数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学最大二分匹配
二分匹配是指图中的一组边以这样的方式选择，以致于集合中的任何两条边都不会共享一个端点。最大匹配是匹配的最大边数。
找到最大匹配后，我们不能再添加任何边。如果将一条边添加到最大匹配图中，它将不再是匹配。对于二分图，可以存在多个最大匹配。
输入和输出
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, visited, assign)
输入： 起始节点、已访问列表用于追踪、分配列表将节点分配给另一个节点。
输出 − 当可能为顶点 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
//when v is not assigned or previously assigned
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
更新日期： 16-6 月 - 2020
8K+ 浏览
广告