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

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

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

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

``````// 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;

// vertex 'u'. The value of u ranges from 1 to m.
// 0 is used for dummy vertex

// These are basically pointers to arrays needed
// for hopcroftKarp()
int *pairU, *pairV, *dist;

public :
BipGraph( int m, int n); // Constructor

// 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;
{
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;
{
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)
{
}

// Driver Program
int main()
{
BipGraph g(4, 4);

cout << "Size of maximum matching is " << g.hopcroftKarp();

return 0;
}``````

``Size of maximum matching is 4``

• 回顶