Algorytm Hopcrofta-Karpa

RNO-Wiki

Przeczytaj najpierw artykuł, w którym omawiana jest dwudzielność grafu.

Niech zbiór wierzchołków grafu G podzielony będzie na wierzchołki górne (mężczyźni) i dolne (kobiety). Algorytm Hopcrofta-Karpa można zapisać bardzo krótko za pomocą wyszukiwania wszystkich ścieżek alternujących pewnej długości. W tym artykule rozgryziemy nieco to co jest ukryte w tym wyszukiwaniu ścieżek alternujących.

Niech n oznacza liczbę mężczyzn, a m --- kobiet. Dla każdego mężczyny i dla każdej kobiety będziemy pamiętali czy jest skojarzona i z kim.

Algorytm

Algorytm będzie miał postać

 do
 {
     1. ETAP_BFS // wyszukiwanie najkrótszej ścieżki alternującej
     2. ETAP_DFS // wyszukiwanie wszystkich ścieżek najkrótszych ścieżek
 }
 while ( wynik kroku 2. == true );

ETAP_BFS

W tym etapie będziemy próbowali znaleźć ścieżkę alternującą o najkrótszej długości. W tym celu użyjemy przeszukiwania wszerz BFS, gdyż przegląda ono ścieżki wierzchołki w kolejności zgodnej z odległością.

Będziemy nadawali mężczyznom kolejne numery przy odwiedzaniu przez BFS

 1. wszystkim mężczyznom nadaj odległość -1

Teraz

 2. niech Q będzie pustą kolejką
 3. wszystkich nieskojarzonych jeszcze mężczyzn wstaw do kolejki Q oraz nadaj im odległość 0

A teraz zwyczajny BFS

 4. dopóki Q nie jest pusta
 4.1. wyciągnij pierwszego mężczyznę x z kolejki Q
 4.2. dla każdej kobiety y, którą zna x wykonaj:
        jeśli y jest skojarzona z mężczyzną z
        oraz jeśli z ma przypisaną odległość -1 (nie był jeszcze odwiedzony), to
            nadaj z odległość o jeden większą niż ma odległość x
            wstaw z do kolejki Q

ETAP_DFS

Najpierw wszystkie wierzchołki oznaczamy jako nieodwiedzone

 1. każdego mężczyznę oznacz jako nieodwiedzonego

Teraz będziemy wywoływać serię DFS'ów w każdym nieodwiedzonym jeszcze wierzchołku

 2. dla każdego mężczyzny x wykonaj:
      jeśli x nie jest skojarzony, to wykonaj DFS(x)

Wynikiem etapu ETAP_DFS jest wartość logiczna true lub false w zależności od tego, czy choć jeden DFS w powyższej pętli zwrócił wartość true.

Procedura DFS

Pozostaje jeszcze omówić działanie procedury DFS. Będziemy w niej korzystali z odległości, jakie obliczył nam etap BFS.

 DFS(x)
 {
   zaznacz mężczyznę x jako odwiedzonego
   dla każdej znanej mu kobiety y wykonaj:
     jeśli y nie jest skojarzona, to skojarz x z y i zwróć true
     niech z oznacza mężczyznę, który jest skojarzony z y
     jeśli z nie jest jeszcze odwiedzony oraz odległość z jest o jeden większa niż odległość x, to
        wykonaj DFS(z)
        jeśli wynik to true to skojarz x z y i zwróć true
   zwróć false
 }