Diskuse:Dinicův algoritmus
Poslední komentář: před 5 lety od uživatele Hippo.69 v tématu „Připsal jsem do složitosti zmínku o implementaci pomocí datových struktur“
Připsal jsem do složitosti zmínku o implementaci pomocí datových struktur
editovatNapsal jsem to tak stručně, jak to je na anglické verzi, (vhodnými strukturami jsou St (Sleator Tarjan) stromy, Fredercksonova clusterizace, případně Top trees) Hippo.69 (diskuse) 15. 10. 2018, 15:33 (CEST)
Dinicův algoritmus pro nalezení maximálního párování
editovatProblém maximálního párování v bipartitním grafu lze převést na hledání maximálního toku, pokud se zdroj napojí na partitu A, hrany se zorientují z A do B, vrcholy partity B se napojí na stok. Všem hranám se přidělí kapacita velikosti jedna - tedy hrana vede nebo nevede.
Hlavní část algoritmu v C++:
int pocetVrcholu;
vector<int> * graf;
int zdroj=0;
int stok=pocetVrcholu+1;
struct Stav {
int predchozi;
int vrchol;
int index;
Stav(){}
Stav(int vrchol, int prev) : predchozi(prev), vrchol(vrchol), index(-1) {}
};
void main(){
bool * navstiveno = new bool[pocetVrcholu+2]; //false
bool zmena = true;
while(zmena){
zmena = false;
for(int i=0; i<pocetVrcholu+2; i++) navstiveno[i] = false;
stack<Stav> zasobnik;
zasobnik.push(Stav(zdroj, -1)); //začínáme DFS
navstiveno[zdroj] = true;
while(zasobnik.size()){
Stav & stav = zasobnik.top();
stav.index++;
if(stav.index >= graf[stav.vrchol].size()){
zasobnik.pop();
if(!zasobnik.size()) break;
continue;
}
int hranaKam = graf[stav.vrchol][stav.index];
//hledej
if(navstiveno[hranaKam])
continue; //index++;
if(hranaKam != stok){
zasobnik.push(Stav(hranaKam, stav.vrchol));
navstiveno[hranaKam] = true;
continue;
}
//našli jsme stok - nasytíme cestu = poootáčíme hrany ----------
zmena = true;
int kam = stok;
Stav x;
while(zasobnik.size()){
x = zasobnik.top();
graf[x.vrchol].erase(graf[x.vrchol].begin()+x.index);
graf[kam].push_back(x.vrchol);
kam = x.vrchol;
zasobnik.pop();
}
zasobnik.push(x);//poslední si necháme
}//endwhile fronta
}//endwhile změna
}
Jedno z maximálních párování je potom na hranách, které vedou z B do A.
Až ten algoritmus přepíšu více elegantně, tak přidám na hlavní stránku. Zbytovsky 29. 12. 2010, 22:28 (UTC)