双向匹配是这样选择图形中的一组边的,即该组中没有两个边共享端点。最大匹配与最大边数匹配。
找到最大匹配时,我们无法添加另一条边。如果将一条边添加到最大匹配图,则它不再是匹配。对于二部图,最大匹配可能不止一个。
Input: The adjacency matrix. 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 Output: Maximum number of applicants matching for job: 5
bipartiteMatch(u,已访问,已分配)
输入: 起始节点,访问列表以进行跟踪,分配列表以将节点分配给另一个节点。
输出-如果可以匹配顶点u,则返回true。
Begin for all vertex v, which are adjacent with u, do if v is not visited, then mark v as visited if v is not assigned, or bipartiteMatch(assign[v], visited, assign) is true, then assign[v] := u return true done return false End
maxMatch(图)
输入- 给定的图形。
输出-匹配的最大数目。
Begin initially no vertex is assigned count := 0 for all applicant u in M, do make all node as unvisited if bipartiteMatch(u, visited, assign), then increase count by 1 done End
#include <iostream> #define M 6 #define N 6 using namespace std; bool bipartiteGraph[M][N] = { //A graph with M applicant and N jobs {0, 1, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1} }; bool bipartiteMatch(int u, bool visited[], int assign[]) { for (int v = 0; v < N; v++) { //for all jobs 0 to N-1 if (bipartiteGraph[u][v] && !visited[v]) { //when job v is not visited and u is interested visited[v] = true; //mark as job v is visited //当v未分配或先前分配 if (assign[v] < 0 || bipartiteMatch(assign[v], visited, assign)) { assign[v] = u; //assign job v to applicant u return true; } } } return false; } int maxMatch() { int assign[N]; //an array to track which job is assigned to which applicant for(int i = 0; i<N; i++) assign[i] = -1; //initially set all jobs are available int jobCount = 0; for (int u = 0; u < M; u++) { //for all applicants bool visited[N]; for(int i = 0; i<N; i++) visited[i] = false; //initially no jobs are visited if (bipartiteMatch(u, visited, assign)) //when u get a job jobCount++; } return jobCount; } int main() { cout << "Maximum number of applicants matching for job: " << maxMatch(); }
输出结果
Maximum number of applicants matching for job: 5