Diskuse:Dinicův algoritmus

Připsal jsem do složitosti zmínku o implementaci pomocí datových struktur

Napsal 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í

Problé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)