Wie funktioniert der Hopcroft-Karp-Algorithmus?
Ich arbeite gerade an einem Projekt, um den Hopcroft-Karp-Algorithmus bildlich zu erklären.
Ich verwende den Pseudocode aus dem Wikipedia-Artikel .
Ich habe diesen Algorithmus auch in Stack Overflow in Python
implementiertDas wäre fantastisch, wenn ich den Algorithmus nicht komplett verstehen müsste, um ihn zu benutzen.
Meine Fragen lauten wie folgt: Was bedeutet das Array Dist [] im Pseudo-Code und wie erfolgt die Layerung des Graphen in der Breitensuche? Ich verstehe die Arbeitsweise der DFS.
Vielen Dank im Voraus.
2 Antworten
Der Standard BFS erstellt Layer, bei denen Knoten in aufeinanderfolgenden Layern in einem Abstand von genau einem Abstand voneinander liegen zwischen den Knoten aufeinanderfolgender Schichten gibt es einen Pfad der Länge 1).
%Vor% Dieser Code initialisiert also die erste Ebene der BFS-Struktur und setzt alle " freien Knoten " v (dh Pair[v] == NIL ) in der Entfernung 0 sein.
und dieser Code baut den BFS-Baum Schicht für Schicht weiter auf, für Knoten u , die Nachbarn von v sind (bei Entfernung genau eins).
Dist[] ist nur eine Möglichkeit, die Entfernungen von Knoten zur anfänglichen Ebene des BFS zu verwalten.
Hier ist ein komplett annotierter Code für den Hopcroft Karp Algorithmus, den ich geschrieben habe. Der unten stehende annotierte Code hilft hoffentlich, jeden Winkel dieses schönen Algorithmus zu erklären. Es ist in C #, aber Code kann leicht in C ++ / Java übersetzt werden. Sie können die Testfälle auch auf meinem Github Repo finden.
Hinweis : Ich habe auch die zusammengefasste Version dieser Erklärung und das folgende Diagramm in Wikipedia-Artikel .
