Hopcroft–Karp最大匹配算法S2（代码实现）

我们强烈建议你先参考以下帖子。

Hopcroft–Karp最大匹配算法S1(简介)

在开始实现之前, 没有什么要注意的重要事情。

1. 我们要找到一条增长之路(在匹配边缘和不匹配边缘之间交替的路径, 并具有自由顶点作为起点和终点)。
2. 找到替代路径后, 我们需要将找到的路径添加到现有匹配项。这里添加路径的意思是, 使该路径上的先前匹配边缘为不匹配, 而先前未匹配边缘为匹配。

这个想法是使用BFS(宽度优先搜索)来查找增强路径。由于BFS逐级遍历, 因此它用于将图形划分为匹配的边缘和不匹配的边缘。添加了一个虚拟顶点NIL, 该虚拟顶点NIL连接到左侧的所有顶点和右侧的所有顶点。以下数组用于查找扩充路径。到NIL的距离初始化为INF(无限)。如果我们从虚拟顶点开始, 然后使用不同顶点的交替路径返回到虚拟顶点, 那么就有一条增加路径。

1. pairU []：大小为m + 1的数组, 其中m是二分图左侧的顶点数。 pairU [u]如果u匹配则在右侧存储一对u, 否则存储NIL。
2. pairV []：大小为n + 1的数组, 其中n是二分图右侧的顶点数。 pairV [v]如果v匹配, 则在左侧存储v对, 否则存储NIL。
3. dist []：大小为m + 1的数组, 其中m是二分图左侧的顶点数。如果u不匹配, 则dist [u]初始化为0, 否则初始化为INF(无限)。 NIL的dist []也初始化为INF

一旦找到扩充路径, 就可以使用DFS(深度优先搜索)将扩充路径添加到当前匹配项中。 DFS只需遵循BFS的距离数组设置即可。如果v在BFS中紧挨着u, 它将填充pairU [u]和pairV [v]中的值。

下面是上述Hopkroft Karp算法的C ++实现。

// C++ implementation of Hopcroft Karp algorithm for
// maximum matching
#include<bits/stdc++.h>
using namespace std;
#define NIL 0
#define INF INT_MAX
  
// A class to represent Bipartite graph for Hopcroft
// Karp implementation
class BipGraph
{
     // m and n are number of vertices on left
     // and right sides of Bipartite Graph
     int m, n;
  
     // adj[u] stores adjacents of left side
     // vertex 'u'. The value of u ranges from 1 to m.
     // 0 is used for dummy vertex
     list< int > *adj;
  
     // These are basically pointers to arrays needed
     // for hopcroftKarp()
     int *pairU, *pairV, *dist;
  
public :
     BipGraph( int m, int n); // Constructor
     void addEdge( int u, int v); // To add edge
  
     // Returns true if there is an augmenting path
     bool bfs();
  
     // Adds augmenting path if there is one beginning
     // with u
     bool dfs( int u);
  
     // Returns size of maximum matcing
     int hopcroftKarp();
};
  
// Returns size of maximum matching
int BipGraph::hopcroftKarp()
{
     // pairU[u] stores pair of u in matching where u
     // is a vertex on left side of Bipartite Graph.
     // If u doesn't have any pair, then pairU[u] is NIL
     pairU = new int [m+1];
  
     // pairV[v] stores pair of v in matching. If v
     // doesn't have any pair, then pairU[v] is NIL
     pairV = new int [n+1];
  
     // dist[u] stores distance of left side vertices
     // dist[u] is one more than dist[u'] if u is next
     // to u'in augmenting path
     dist = new int [m+1];
  
     // Initialize NIL as pair of all vertices
     for ( int u=0; u<=m; u++)
         pairU[u] = NIL;
     for ( int v=0; v<=n; v++)
         pairV[v] = NIL;
  
     // Initialize result
     int result = 0;
  
     // Keep updating the result while there is an
     // augmenting path.
     while (bfs())
     {
         // Find a free vertex
         for ( int u=1; u<=m; u++)
  
             // If current vertex is free and there is
             // an augmenting path from current vertex
             if (pairU[u]==NIL && dfs(u))
                 result++;
     }
     return result;
}
  
// Returns true if there is an augmenting path, else returns
// false
bool BipGraph::bfs()
{
     queue< int > Q; //an integer queue
  
     // First layer of vertices (set distance as 0)
     for ( int u=1; u<=m; u++)
     {
         // If this is a free vertex, add it to queue
         if (pairU[u]==NIL)
         {
             // u is not matched
             dist[u] = 0;
             Q.push(u);
         }
  
         // Else set distance as infinite so that this vertex
         // is considered next time
         else dist[u] = INF;
     }
  
     // Initialize distance to NIL as infinite
     dist[NIL] = INF;
  
     // Q is going to contain vertices of left side only. 
     while (!Q.empty())
     {
         // Dequeue a vertex
         int u = Q.front();
         Q.pop();
  
         // If this node is not NIL and can provide a shorter path to NIL
         if (dist[u] < dist[NIL])
         {
             // Get all adjacent vertices of the dequeued vertex u
             list< int >::iterator i;
             for (i=adj[u].begin(); i!=adj[u].end(); ++i)
             {
                 int v = *i;
  
                 // If pair of v is not considered so far
                 // (v, pairV[V]) is not yet explored edge.
                 if (dist[pairV[v]] == INF)
                 {
                     // Consider the pair and add it to queue
                     dist[pairV[v]] = dist[u] + 1;
                     Q.push(pairV[v]);
                 }
             }
         }
     }
  
     // If we could come back to NIL using alternating path of distinct
     // vertices then there is an augmenting path
     return (dist[NIL] != INF);
}
  
// Returns true if there is an augmenting path beginning with free vertex u
bool BipGraph::dfs( int u)
{
     if (u != NIL)
     {
         list< int >::iterator i;
         for (i=adj[u].begin(); i!=adj[u].end(); ++i)
         {
             // Adjacent to u
             int v = *i;
  
             // Follow the distances set by BFS
             if (dist[pairV[v]] == dist[u]+1)
             {
                 // If dfs for pair of v also returns
                 // true
                 if (dfs(pairV[v]) == true )
                 {
                     pairV[v] = u;
                     pairU[u] = v;
                     return true ;
                 }
             }
         }
  
         // If there is no augmenting path beginning with u.
         dist[u] = INF;
         return false ;
     }
     return true ;
}
  
// Constructor
BipGraph::BipGraph( int m, int n)
{
     this ->m = m;
     this ->n = n;
     adj = new list< int >[m+1];
}
  
// To add edge from u to v and v to u
void BipGraph::addEdge( int u, int v)
{
     adj[u].push_back(v); // Add u to v’s list.
}
  
// Driver Program
int main()
{
     BipGraph g(4, 4);
     g.addEdge(1, 2);
     g.addEdge(1, 3);
     g.addEdge(2, 1);
     g.addEdge(3, 2);
     g.addEdge(4, 2);
     g.addEdge(4, 4);
  
     cout << "Size of maximum matching is " << g.hopcroftKarp();
  
     return 0;
}

输出如下：

Size of maximum matching is 4

以上实现主要是从Wiki页面提供的算法中采用的。Hopcroft Karp算法.

本文作者：拉胡尔·古普塔(Rahul Gupta)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。