Algoritmul hopcroft karp

Algoritmul Hopcroft-Karp este un algoritm care rezolva asa numita problema a cuplajului maxim intr-un graf bipartit. Datele de intrare de care avem nevoie sunt numarul nodurilor din stanga si care sunt acestea, numarul de noduri si care sunt acestea din dreapta, numarul de muchii si ce noduri leaga acestea. Algoritmul consta intr-o bucla cat_timp in care pentru toate nodurile din partea stanga se verifica daca le-am gasit pereche in dreapta la pasii anteriori. Daca nu am gasit atunci excutam urmatorul algoritm recursiv care este o parcurgere in adancime:

  procedura DFS(X)  //Atentie! X este mereu din aceiasi partea a grafului bipartit(in acest caz stanga)
       daca X a fost marcat ca vizitat   //este acelasi lucru cu nu l-am cuplat pe X 
               returneaza: nu i-am gasit pereche lui X
       Marcheaza X ca vizitat
       Cautam intre vecinii nodului X un nod necuplat
            Daca exista atunci il cuplam!
            returneaza: i-am gasit pereche lui X
       Pentru fiecare dintre vecinii Y ai lui X  
            Daca DFS(nod cuplat cu Y) i-a gasit pereche nodului cuplat cu Y
            returneaza: i-am gasit pereche lui X
  
  Returneaza nu i-am gasit pereche lui Y          

  Procedura Hopcroft Karp
        nu_am_terminat=1
        numar_de_cupluri
        cat_timp nu_am_terminat=1
                 nu_am_terminat=0
                 marcheaza toate nodurile din stanga ca nevizitate
                 pentru oricare nod X din stanga
                        daca nu a fost cuplat cu un nod din dreapta
                             daca DFS(X) i-a gasit pereche lui X 
                                  nu_am_terminat=1
                                  numar_de_cupluri= numar_de_cupluri+1
                       

Completari

- vectorul de noduri nevizitatea este necesar pentru ca DFS-ul sa nu cicleze la infinit;

- este evident ca la apelul din procedura Hopcroft Karp a Dfs-ului, nodul X va fi mereu marcat ca nevizitat;

- din acest lucru putem trage concluzia ca la fiecare apel al functiei DFS este cuplat cel putin 1 nod;

- daca la apelul procedurii DFS din DFS nodul X este vizitat inseamna ca acesta a fost cuplat, iar daca am rupe cuplajul X-ului cu perechea sa din dreapta pentru a o cupla pe aceasta cu un alt nod, solutia nu va fi imbunatita si este convenabil sa lasam asa

- la acest caz ajungem cand toate nodurile au fost cuplate cu exceptia celui cu care am apelat din procedura Hopcroft Karp DFS-ul

Complexitate

Algoritmul DFS(si evident ultimul for din procedura Hopcroft Karp) are complexitatea O(S+D+M) si s-a demonstrat ca ciclari ale buclei cat_timp este cel mult O(√(S+D)) asadar algoritmul Hopcroft Karp are o complexitatea in cel mai rau caz de O(M √(S+D)) mai buna decat daca am trata problema ca una de flux maxim si am folosi algoritmi precum Edmonds-Karp sau Dinic care au coplexitatea O(M*(S+D))