Quelltext der Seite Algorithmus von Hopcroft und Karp

Der '''[[Algorithmus]] von Hopcroft und Karp''' ([[1973]] von [[John E. Hopcroft]] und [[Richard M. Karp]] entwickelt) dient in der [[Graphentheorie]] zur Bestimmung eines [[Matching (Graphentheorie)|Matchings]] mit maximaler Kardinalität in einem [[Bipartiter Graph|bipartiten Graphen]]. Er geht aus von dem Matching, die keine Kanten enthält, und konstruiert dazu [[Alternierender Pfad|alternierende Pfade]] zwischen noch ungepaarten [[Knoten (Graphentheorie)|Knoten]]. Jeder solche [[Pfad (Graphentheorie)|Pfad]] liefert eine Vergrößerung (Augmentierung) des Matchings um eine [[Kante (Graphentheorie)|Kante]].

== Augmentierende Pfade ==
Ist zu einem [[Graph (Graphentheorie)|Graphen]] mit Kantenmenge <math>E</math> ein Matching <math>M \subset E</math> gegeben, so betrachten wir zusammenhängende Teilgraphen, die [[Baum (Graphentheorie)|Bäume]] sind, also keinen [[Zyklus (Graphentheorie)|Zyklus]] enthalten und die bestehen aus

* einem ungepaarten [[Knoten (Graphentheorie)|Knoten]] als ''Wurzel'',
* gepaarten Knoten, die sich von der Wurzel aus innerhalb des [[Baum (Graphentheorie)|Baumes]] erreichen lassen auf ''alternierenden'' [[Pfad (Graphentheorie)|Pfaden]] gerader Kantenzahl. ''Alternierend'' heißt, dass die Kanten des Pfades abwechselnd zu <math>M</math> gehören und nicht zu <math>M</math> gehören. Diese Knoten haben also geraden Abstand von der Wurzel.
* allen [[Knoten (Graphentheorie)|Knoten]] und [[Kante (Graphentheorie)|Kanten]] entlang der alternierenden [[Pfad (Graphentheorie)|Pfade]]. Dadurch kommen auch Knoten hinzu, die ungeraden Abstand von der Wurzel haben.

Eine [[Vereinigungsmenge]] solcher Bäume, die keine gemeinsamen Knoten haben, heißt ''Wald''.

Wenn Knoten <math>x</math> und <math>y</math> aus zwei verschiedenen Bäumen des Waldes, die jeweils geraden Abstand von ihrer Wurzel haben, durch die Kante <math>xy\in E</math> verbunden sind, so kann diese Kante nicht zu <math>M</math> gehören, denn die Knoten sind ja schon durch je eine andere Kante innerhalb des Baumes gepaart, es sei denn, es handelt sich um die Wurzel, die sowieso ungepaart ist. Der Pfad mit Kantenmenge <math>P</math> von der Wurzel des einen Baumes über <math>xy</math> zur Wurzel des anderen Baumes ist dann ein alternierender Pfad mit ungepaartem Anfangs- und Endknoten. Ein solcher Pfad wird <math>M</math>''-[[augmentierender Pfad]]'' genannt, denn <math>(M \setminus P) \cup (P \setminus M)</math> ist ein Matching, das eine Kante mehr enthält als <math>M</math>.

Umgekehrt gilt, dass ein Matching <math>M'</math>, das mehr Kanten enthält als <math>M</math>, einen Teilgraph mit Kantenmenge <math>(M \setminus M') \cup (M' \setminus M)</math> ergibt, in dem alle Pfade zwischen <math>M</math> und <math>M'</math> alternieren, und von denen mindestens <math>|M'| - |M|</math> Pfade <math>M</math>-augmentierend ohne gemeinsame Knoten sein müssen. <math>M</math> ist also genau dann ein maximales Matching, wenn es keinen <math>M</math>-augmentierenden Pfad gibt.

=== Ungarische Wälder ===
Bei der Definition der betrachteten Wälder wurde bisher nicht vorausgesetzt, dass ein [[bipartiter Graph]] vorliegt. In einem bipartiten Graphen <math>(U\cup V,E)</math> gilt aber mehr: Dort liegen die [[Knoten (Graphentheorie)|Knoten]] geraden Abstandes von ihrer Wurzel in <math>U</math> oder <math>V</math>, je nachdem wo die Wurzel auch liegt. Wenn es dann im Wald keine zwei Knoten <math>x</math> und <math>y</math> mit <math>xy\in E</math> wie im letzten Abschnitt gibt und der Wald auch nicht mehr unter Einhaltung der genannten Eigenschaften vergrößert werden kann, heißt er ein ''ungarischer Wald''. Wegen der Bipartitheit lässt sich dann zeigen, dass das Matching genau dann ein maximales Matching ist, wenn es zu ihm einen ungarischen Wald gibt.

=== Algorithmus ===
Der folgende [[Algorithmus]] ist eine Vorstufe zum Algorithmus von Hopcroft und Karp. Er konstruiert zu einem [[Bipartiter Graph|bipartiten Graphen]] mit Matching <math>M</math> einen Wald mit den genannten Eigenschaften, der

* entweder ein ungarischer Wald ist
* oder einen <math>M</math>-[[Augmentierender Pfad|augmentierenden Pfad]] liefert.

# Beginne mit dem Wald, der alle ungepaarten [[Knoten (Graphentheorie)|Knoten]] als Wurzeln enthält, aber keine [[Kante (Graphentheorie)|Kanten]].
# Suche eine Kante von einem Knoten <math>x</math> des Waldes mit geradem Abstand von seiner Wurzel zu einem Knoten <math>y</math>, der nicht zum Wald gehört oder geraden Abstand von seiner Wurzel hat. Falls es keinen solchen Knoten mehr gibt, ist der Wald ein ungarischer Wald. Beende den Algorithmus.
# Falls <math>y</math> geraden Abstand von seiner Wurzel hat, gibt es einen Pfad gerader Länge von einem ungepaarten Knoten <math>z</math> nach <math>y</math>. Gib den <math>M</math>-augmentierenden Pfad von <math>x</math> über <math>y</math> nach <math>z</math> zurück und beende den Algorithmus.
# Falls <math>y</math> nicht zum Wald gehört, ist <math>y</math> gepaart, etwa <math>yz \in M</math>: Füge die Knoten <math>y</math> und <math>z</math> sowie die Kanten <math>xy</math> und <math>yz</math> zum Wald hinzu und gehe zurück zu Schritt&nbsp;2.

Zu Beginn wird der Algorithmus mit <math>M = \emptyset</math> ausgeführt. Falls er in Schritt 3 mit einem <math>M</math>-augmentierenden Pfad <math>P</math> endet, wird <math>M</math> durch <math>(M \setminus P) \cup (P \setminus M)</math> ersetzt und der Algorithmus erneut durchgeführt. Der Fall, dass der Algorithmus in Schritt 2 mit einem ungarischen Wald endet, wobei dann <math>M</math> eine maximales Matching ist, muss nach spätestens <math>(|U|+|V|)/2</math> Durchläufen des Algorithmus eintreten, weil das Matching im anderen Fall jeweils um zwei Knoten vergrößert wird. Die Laufzeit bei einmaliger Durchführung des Algorithmus ist proportional zur Kantenzahl <math>|E|</math>, die Gesamtlaufzeit bei mehrmaliger Durchführung also proportional zum Produkt aus Kanten- und Knotenzahl.

== Beispiel ==
[[Datei:Hopcroft-Karp-exemple-premiere-partie.jpg|rechts|rahmenlos]]
[[Datei:Hopcroft-Karp-exemple-deuxieme-partie.jpg|rechts|rahmenlos]]
Der [[Bipartiter Graph|bipartite Graph]] im Beispiel hat 10 Knoten und 10 Kanten. Im linken Teil sind vor der ersten Phase alle [[Knoten (Graphentheorie)|Knoten]] frei, das Matching ist leer. Alle [[Augmentierender Pfad|augmentierenden Pfade]] werden auf eine einzelne Kante zwischen einem Knoten in <math>U</math> und einem Knoten in <math>V</math> reduziert. Eine [[Breitensuche]] wählt zum Beispiel die [[Kante (Graphentheorie)|Kanten]] <math>(u_0, v_0), (u_1, v_4), (u_2, v_2), (u_4, v_1)</math>, indem sie für jeden Knoten in <math>U</math> den freien Knoten in <math>V</math> mit dem kleinsten Index auswählt. Diese Menge von Pfaden ist maximal, alle haben die gleiche Länge 1, das erhaltene Matching hat die Größe 4 und es verbleiben zwei freie Knoten, <math>u_3</math> und <math>v_3</math>.

In der zweiten Phase geht es darum, die [[Pfad (Graphentheorie)|Pfade]] mit minimaler Längenzunahme ausgehend vom einzigen freien Knoten von <math>U</math> oder vom einzigen freien Knoten von <math>V</math> zu finden. Der angegebene Pfad <math>(u_3, v_0, u_0, v_1, u_4, v_3)</math> wechselt zwischen schwarzen Kanten außerhalb des Matchings und roten Kanten innerhalb des Matchings. Er hat die Länge 5. Wir können sehen, dass es keinen Pfad der Länge 3 gibt, aber es gibt einen Pfad der Länge 7, nämlich <math>(u_3, v_4, u_1, v_0, u_0, v_1, u_4, v_3)</math>. Das Matching, das sich aus der [[Symmetrische Differenz|symmetrischen Differenz]] des vorherigen Matchings mit dem Weg der Länge 5 ergibt, ergibt im Beispiel das Matching der Größe 5. Es ist maximal, weil es keine freien Knoten mehr gibt.

== Gleichzeitige Augmentierung mehrerer Pfade ==
Die [[Laufzeit (Informatik)|Gesamtlaufzeit]] des [[Algorithmus]] kann verringert werden, wenn mehrere <math>M</math>-[[Augmentierender Pfad|augmentierende Pfade]] gleichzeitig betrachtet werden. Es sei <math>l(M)</math> die Länge des kürzesten <math>M</math>-augmentierenden Pfades. Wir betrachten <math>M</math>-augmentierende knotendisjunkte Pfade <math>P_1, \ldots, P_m</math> der Länge <math>l(M)</math>, denen sich kein weiterer <math>M</math>-augmentierender Pfad der Länge <math>l(M)</math> knotendisjunkt hinzufügen lässt. Dann lässt sich zeigen, dass
:<math>l((M \setminus(P_1 \cup \ldots \cup P_m)) \cup ((P_1 \cup \ldots \cup P_m) \setminus M)) > l(M)</math>

Der genannte Algorithmus kann so zum Algorithmus von Hopcroft und Karp erweitert werden, dass er nicht nur ''einen'' augmentierenden Pfad zurückgibt, sondern eine Menge augmentierender Pfade wie gerade betrachtet. Dazu müssen Schritt 2 und 3 als [[Breitensuche]] durchgeführt werden, wobei die konstruierten Pfade im Wald erst dann verlängert werden, wenn keine neuen Pfade der bisherigen Länge mehr zu finden sind. Sobald ein Pfad zu einem ungepaarten Knoten führt, also ein augmentierender Pfad ist, brauchen keine Pfade noch größerer Länge mehr betrachtet zu werden.

Ist <math>M'</math> ein maximales Matching und <math>n=|U|+|V|</math>, so liefert der so erweiterte Algorithmus nach <math>\sqrt n</math> Durchläufen ein Matching <math>P</math> mit <math>l(M) \ge \sqrt{n}</math> und <math>|M'|-|M|</math> knotendisjunkte <math>M</math>-augmentierende Pfade, deren Länge mindestens <math>l(M) \ge \sqrt{n}</math> ist. Weil keiner der <math>n</math> Knoten in zweien dieser Pfade enthalten ist, muss <math>|M'| - |M| \le \sqrt{n}</math> sein, also muss das maximale Matching nach spätestens weiteren <math>\sqrt{n}</math> Durchläufen erreicht sein. Die Gesamtlaufzeit des Algorithmus von Hopcroft und Karp ist demnach proportional zum Produkt aus Kantenzahl und Quadratwurzel der Knotenzahl.

== Vergleich mit anderen Algorithmen ==
Für dünne [[Graph (Graphentheorie)|Graphen]] weist der Algorithmus von Hopcroft und Karp weiterhin die beste [[Worst Case|Worst-Case]]-[[Laufzeit (Informatik)|Laufzeit]] auf. Für dichte Graphen erzielt ein neuerer [[Algorithmus]] eine etwas bessere [[Laufzeit (Informatik)|Laufzeit]].<ref>H. Alt, N. Blum, K. Mehlhorn, M. Paul, Institute of Computing, University of Campinas: [https://www.sciencedirect.com/science/article/abs/pii/002001909190195N?via%3Dihub Computing a maximum cardinality matching in a bipartite graph in time]</ref>

Dieser [[Algorithmus]] basiert auf der Verwendung des [[Goldberg-Tarjan-Algorithmus]]. Wenn das durch diesen Algorithmus erzeugte [[Matching (Graphentheorie)|Matching]] nahezu optimal ist, wird zum Algorithmus von Hopcroft und Karp gewechselt. Mehrere Autoren haben experimentelle Vergleiche von Algorithmen für [[bipartite Matchings]] durchgeführt. Ihre Ergebnisse zeigen tendenziell, dass der Algorithmus von Hopcroft und Karp in der Praxis nicht so gut ist wie in der Theorie. Er wird sowohl durch einfachere Strategien für die Suche nach augmentierenden Pfaden als auch durch [[Push-Relabel-Algorithmus|Push-Relabel]]-Techniken übertroffen.<ref>Joao C. Setubal, Institute of Computing, University of Campinas: [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.3539 Sequential and Parallel Experimental Results with Bipartite Matching Algorithms]</ref>

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C++]] zeigt die Implementierung des Algorithmus von Hopcroft und Karp für einen [[Bipartiter Graph|bipartiten Graphen]]. Der bipartite Graph wird als [[Klasse (Objektorientierung)|Klasse]] ''BipartiteGraph'' deklariert. Die [[Methode (Programmierung)|Methode]] ''HopcroftKarp'' verwendet [[Breitensuche]] und [[Tiefensuche]]. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''main'' verwendet, die die Liste der markierten Knoten auf der Konsole ausgibt.<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/hopcroft-karp-algorithm-for-maximum-matching-set-2-implementation/ Hopcroft–Karp Algorithm for Maximum Matching]</ref><syntaxhighlight lang="c++">
#include <list>
#include <queue>
#include <iostream>

using namespace std;

#define NIL 0
#define INF INT_MAX

// Deklariert den Datentyp für die Knoten des Graphen
struct Node
{
    int index;
    string value;
    Node* next;
};

// Deklariert die Klasse für den bipartiten Graphen
class BipartiteGraph
{
    int count1, count2; // Anzahl der Knoten auf der linken und rechten Seite des bipartiten Graphen
    list<Node>* adjacencyList; // Anzahl der Knoten auf der linken und rechten Seite des bipartiten Graphen
    Node* pair1, * pair2; int distance[]; // Basiszeiger, die in der Methode HopcroftKarp verwendet werden

// Deklariert die Interfaces für die Methoden
public:
    BipartiteGraph(int count1, int count2); // Konstruktor
    void AddEdge(Node* startNode, Node* targetNode);
    bool BreadthFirstSearch();
    bool DepthFirstSearch(Node* startNode);
    int HopcroftKarp();
};

// Gibt die Matchingzahl des maximalen Matching zurück
int BipartiteGraph::HopcroftKarp()
{
    pair1 = new Node[count1 + 1]; // Speichert ein Paar von Knoten, wobei pair1[u] eine Ecke auf der linken Seite des bipartiten Graphen ist. Wenn nicht vorhanden, wird der Nullzeiger NIL gespeichert.
    pair2 = new Node[count2 + 1]; // Speichert ein Paar von Knoten, wobei pair1[v] eine Ecke auf der rechten Seite des bipartiten Graphen ist. Wenn nicht vorhanden, wird der Nullzeiger NIL gespeichert.
    // Initialisiert die Paare mit dem Nullzeiger NIL
    for (int i = 0; i <= count1; i++)
    {
        (&pair1)[i] = NIL;
    }
    for (int i = 0; i <= count2; i++)
    {
        (&pair2)[i] = NIL;
    }
    int result = 0; // Initialisierung
    while (BreadthFirstSearch())
    {
        for (int i = 1; i <= count1; i++)
        {
            Node* node = &pair1[i];
            if (node == NIL && DepthFirstSearch(node))
            {
                result++;
            }
        }
    }
    return result;
}

// Gibt true zurück, wenn es einen augmentierenden Pfad gibt, sonst false
bool BipartiteGraph::BreadthFirstSearch()
{
    queue<Node> nodeQueue;
    for (int i = 1; i <= count1; i++)
    {
        Node* node = &pair1[i];
        if (node == NIL)
        {
            distance[i] = 0;
            nodeQueue.push(*node);
        }
        else
        {
            distance[i] = INF;
        }
    }
    distance[NIL] = INF;
    while (!nodeQueue.empty())
    {
        int currentIndex = nodeQueue.front().index;
        nodeQueue.pop();
        if (distance[currentIndex] < distance[NIL])
        {
            list<Node>::iterator i;
            for (i = adjacencyList[currentIndex].begin(); i != adjacencyList[currentIndex].end(); ++i)
            {
                Node* node = &pair2[(*i).index];
                int index = (*node).index;
                if (distance[index] == INF)
                {
                    distance[index] = distance[currentIndex] + 1;
                    nodeQueue.push(*node);
                }
            }
        }
    }
    return (distance[NIL] != INF);
}

// Gibt true zurück, wenn es einen augmentierenden Pfad mit startNode gibt, sonst false
bool BipartiteGraph::DepthFirstSearch(Node* startNode)
{
    int startIndex = startNode->index; //
    if (startNode != NIL)
    {
        list<Node>::iterator i;
        for (i = adjacencyList[startIndex].begin(); i != adjacencyList[startIndex].end(); ++i)
        {
            Node j = *i;
            if (distance[pair2[startIndex].index] == distance[startIndex] + 1)
            {
                if (DepthFirstSearch(&pair2[startIndex]))
                {
                    pair2[startIndex] = *startNode;
                    pair1[startIndex] = j;
                    return true;
                }
            }
        }
        distance[startIndex] = INF; // Es gibt keinen augmentierenden Pfad, der mit startNode beginnt.
        return false;
    }
    return true;
}

// Konstruktor mit der Anzahl count1 und count2
BipartiteGraph::BipartiteGraph(int count1, int count2)
{
    this->count1 = count1;
    this->count2 = count2;
    adjacencyList = new list<Node>[count1 + 1];
}

// Diese Methode verbindet die Knoten startNode und targetNode miteinander.
void BipartiteGraph::AddEdge(Node* startNode, Node* targetNode)
{
    adjacencyList[(*startNode).index].push_back(*targetNode);
}

// Hauptmethode, die das Programm ausführt
int main()
{
    // Deklariert und initialisiert 4 Knoten
    Node node1 = Node{ 1, "A", NIL };
    Node node2 = Node{ 2, "B", NIL };
    Node node3 = Node{ 3, "C", NIL };
    Node node4 = Node{ 4, "D", NIL };
    // Verbindet Knoten des Graphen miteinander
    BipartiteGraph bipartiteGraph(4, 4);
    bipartiteGraph.AddEdge(&node1, &node2);
    bipartiteGraph.AddEdge(&node1, &node3);
    bipartiteGraph.AddEdge(&node2, &node1);
    bipartiteGraph.AddEdge(&node3, &node2);
    bipartiteGraph.AddEdge(&node4, &node2);
    bipartiteGraph.AddEdge(&node4, &node4);
    cout << "Size of maximum matching is " << bipartiteGraph.HopcroftKarp(); // Ausgabe auf der Konsole
}

</syntaxhighlight>

== Literatur ==
* Hubertus Th. Jongen: ''Optimierung B''. Skript zur Vorlesung. Verlag der Augustinus-Buchhandlung, Aachen, ISBN 3-925038-19-1

== Weblinks ==
* [https://www-m9.ma.tum.de/graph-algorithms/matchings-hopcroft-karp/index_de.html Ein interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus]

== Einzelnachweise ==
<references />

[[Kategorie:Optimierungsalgorithmus|Hopcroft und Karp, Algorithmus von]]
[[Kategorie:Algorithmus (Graphentheorie)|Hopcroft und Karp, Algorithmus von]]