Hopcroft–最大匹配|集2的Karp算法（实现）-yiteyi-C++库

我们强烈建议将以下帖子作为先决条件。 Hopcroft–最大匹配|集1的Karp算法（简介）

null

在我们开始实施之前，有几件重要的事情需要注意。

我们需要 找到一条扩展路径 （在匹配边和不匹配边之间交替的路径，以自由顶点作为起点和终点）。
一旦我们找到了交替的路径，我们需要 将找到的路径添加到现有匹配 .此处添加路径意味着，将此路径上的前一条匹配边设置为不匹配，将前一条不匹配边设置为匹配。

其思想是使用BFS（广度优先搜索）来寻找增广路径。由于BFS逐层遍历，因此它用于将图划分为匹配边和不匹配边的层。添加一个虚拟顶点NIL，该顶点连接到左侧的所有顶点和右侧的所有顶点。下面的数组用于查找扩充路径。到零的距离初始化为INF（无限）。如果我们从虚拟顶点开始，然后使用不同顶点的交替路径返回到它，那么就有一条增广路径。

pairU[]：大小为m+1的数组，其中m是二部图左侧的顶点数。pairU[u]如果u匹配，则在右侧存储一对u，否则为零。
pairV[]：大小为n+1的数组，其中n是二部图右侧的顶点数。如果v匹配，则pairV[v]在左侧存储一对v，否则为零。
dist[]：大小为m+1的数组，其中m是二部图左侧的顶点数。如果不匹配，dist[u]初始化为0，否则初始化为INF（无限）。NIL的dist[]也被初始化为INF

一旦找到增广路径，就会使用DFS（深度优先搜索）将增广路径添加到当前匹配中。DFS只是遵循BFS设置的距离数组。如果在BFS中v与u相邻，则填充pairU[u]和pairV[v]中的值。

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

C++14

                         // 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 matching                       
                                                 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;                       
                         }                       

JAVA

                         // Java implementation of Hopcroft Karp                       
                         // algorithm for maximum matching                       
                         import                                     java.util.ArrayList;                       
                         import                                     java.util.Arrays;                       
                         import                                     java.util.LinkedList;                       
                         import                                     java.util.List;                       
                         import                                     java.util.Queue;                       
           
                         class                                     GFG{                       
           
                         static                                     final                                     int                                     NIL =                                     0                                     ;                       
                         static                                     final                                     int                                     INF = Integer.MAX_VALUE;                       
           
                         // A class to represent Bipartite graph                       
                         // for Hopcroft Karp implementation                       
                         static                                     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<Integer>[] adj;                       
           
                                                 // These are basically pointers to arrays                       
                                                 // needed for hopcroftKarp()                       
                                                 int                                     [] pairU, pairV, dist;                       
           
                                                 // Returns size of maximum matching                       
                                                 int                                     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                       
                                                 Arrays.fill(pairU, NIL);                       
                                                 Arrays.fill(pairV, 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                       
                                                 boolean                                     bfs()                       
                                                 {                       
                                   
                                                 // An integer queue                       
                                                 Queue<Integer> Q =                                     new                                     LinkedList<>();                       
           
                                                 // 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.add(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.isEmpty())                       
                                                 {                       
                                   
                                                 // Dequeue a vertex                       
                                                 int                                     u = Q.poll();                       
           
                                                 // 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                       
                                                 for                                     (                                     int                                     i : adj[u])                       
                                                 {                       
                                                 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.add(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                       
                                                 boolean                                     dfs(                                     int                                     u)                       
                                                 {                       
                                                 if                                     (u != NIL)                       
                                                 {                       
                                                 for                                     (                                     int                                     i : adj[u])                       
                                                 {                       
                                   
                                                 // 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                       
                                                 @SuppressWarnings                                     (                                     "unchecked"                                     )                       
                                                 public                                     BipGraph(                                     int                                     m,                                     int                                     n)                       
                                                 {                       
                                                 this                                     .m = m;                       
                                                 this                                     .n = n;                       
                                                 adj =                                     new                                     ArrayList[m +                                     1                                     ];                       
                                                 Arrays.fill(adj,                                     new                                     ArrayList<>());                       
                                                 }                       
           
                                                 // To add edge from u to v and v to u                       
                                                 void                                     addEdge(                                     int                                     u,                                     int                                     v)                       
                                                 {                       
                                   
                                                 // Add u to v’s list.                       
                                                 adj[u].add(v);                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                   
                                                 BipGraph g =                                     new                                     BipGraph(                                     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                                     );                       
           
                                                 System.out.println(                                     "Size of maximum matching is "                                     +                       
                                                 g.hopcroftKarp());                       
                         }                       
                         }                       
           
                         // This code is contributed by sanjeev2552                       

输出：

Size of maximum matching is 4

上述实现主要采用的是在的Wiki页面上提供的算法霍普克罗夫特-卡普算法 . 本文由 古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章