数据结构
网络
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(graph)
输入 − 给定的图。
输出 − 匹配的最大数。
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
更新于： 2020 年 6 月 16 日
8K+ 浏览量
广告