Bipartitni grah je graf u kojem vrhove možemo podijeliti u dva skupa tako da sve veze idu iz jednog skupa u drugi.
Odnosno, ne postoji veza između čvorova koje smo stavili u isti skup.
To izgleda ovako nekako:
Odaberi najveći mogući broj parova vrhova tako da svaki vrh pripada najviše jednom odabranom paru.
U paru smiju biti samo vrhovi između kojih postoji veza.
Nazovimo dva skupa bipartitnog grafa skup A i skup B.
Na početku ćemo usmjeriti veze tako da pokazuju samo iz A u B.
Za vrijeme trajanja algoritma, okretanje veze tako da vodi iz B u A značit će nam da smo napravili sparivanje dva vrha koja ta veza spaja.
Sve dok možemo, ponavljamo ova dva koraka:
Na kraju očitamo rješenje tako što pronađemo sve veze koje su okrenute od B prema A.
U svakom koraku algoritma povećat ćemo rješenje za 1.
Nacrtaj si jedan put kakav smo opisali gore, i pogledaj što se dogodi kad okreneš sve veze, pa ćeš vidjet!
A možeš pogledat i ovaj primjer.
Predlažem da probaš sam napisati algoritam i rješiti prvi zadatak dan dolje prije nego što pogledaš ovu implementaciju.
Ako nećeš to, onda bar pažljivo pročitaj objašnjenje i shvati ovaj kod, i onda ga napiši sam bez gledanja tu.
je tipična matrica sa nulama i jedinicama:
Osim ovoga, koristimo još dva polja:
U matching funkciji, pokušavamo spariti jedan po jedan vrh.
Nije očito zašto smijemo ići po redu i sparivati jedan po jedan vrh, odnosno zašto nikad ne moramo pokušati spariti neki od vrhova kojeg u prethodnim koracima nismo uspjeli spariti.
Dokaz nije složen i provodi se indukcijom, ali ovdje nećemo ulaziti u njega.
Prije svakog pokušaja sparivanja vrha, popunimo polje bio nulama.
Funkcija dfs poziva se samo sa vrhovima iz skupa A, dakle stalno smo u tom skupu.
Ona vraća jedan ako postoji put od danog vrha do nekog nesparenog vrha iz skupa B.
Pokušavamo pronaći nesparenog susjeda, ili put koji počinje od vrha s kojim je taj susjed sparen (vidi kod).
Ako uspijemo, sparimo tog našeg susjeda s nama i vratimo 1.
Okretanje veza se ovdje naoko nigdje ne vidi, ali se odvija odmotavanjem rekurzije.
int dfs(int node) { if (bio[node]) return 0; bio[node] = 1; for (int i = 0; i < N; ++i) { if (!graph[node][i]) continue; if (matched[i] == -1 || dfs(matched[i])) { matched[i] = node; return 1; } } return 0; } int matching() { int sol = 0; memset(matched, -1, sizeof matched); for (int i = 0; i < N; ++i) { memset(bio, 0, sizeof bio); sol += dfs(i); } return sol; }
Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License