algorithm - Hopcroft-Karp 算法如何工作？

Question

我目前正在进行一个项目，以图形方式解释 Hopcroft-Karp 算法。

我正在使用 Wikipedia article 中的伪代码.

我还在 Stack Overflow 上看到了这个算法的实现 in Python

如果我不必完全理解算法就可以使用它的话，这会非常棒。

我的问题如下:伪代码中的Dist[]数组是什么意思，广度优先搜索中图的分层是怎么做的。我掌握了 DFS 的工作原理。

提前致谢。

Answer 1

标准BFS创建层，使得连续层中的节点之间的距离恰好为 1(即，连续层的节点之间存在长度为 1 的路径)。

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

因此该代码初始化 BFS 树的第一层，将所有“free nodes”v(即 Pair[v] == NIL)设置为距离 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])

此代码继续逐层构建 BFS 树，对于 v 的邻居节点 u(距离恰好为一个)。

Dist[] 只是一种管理从节点到 BFS 初始层的距离的方法