How does the Hopcroft-Karp algorithm work?

Question

I am currently working on a project to pictorially explain the Hopcroft-Karp algorithm.

I am using the pseudo-code from the Wikipedia article.

I have also seen this algorithm implemented on Stack Overflow in Python

This would do fantastically if only I didn't have to understand the algorithm completely to use it.

My questions are as follows: What is the meaning of the Dist[] array in the pseudo-code, and how is the layering of the graph done in the Breadth-First-Search. I have a grasp on the workings of the DFS.

Thanks in advance.

Answer 1

The standard BFS creates layers such that nodes in successive layers are at a distance of exactly 1 apart (i.e. there is a path of length 1 between the nodes of successive layers).

for v in G1
    if Pair[v] == NIL
       Dist[v] = 0
       Enqueue(Q,v)
   else
       Dist[v] = INF

So that code initializes the first layer of the BFS tree, setting all "free nodes" v (i.e. Pair[v] == NIL) to be at distance 0.

while Empty(Q) == false
   v = Dequeue(Q)
   for each u in Adj[v]
        if Dist[ Pair[u] ] == INF
             Dist[ Pair[u] ] = Dist[v] + 1
             Enqueue(Q,Pair[u])

and this code continues on building the BFS tree layer by layer, for nodes u that are neighbors of v (at distance exactly one).

Dist[] is just a way to manage the distances from nodes to the initial layer of the BFS