二分图最大匹配算法(Hungarian Algorithm)
这个算法的操作与原理及其数学证明都很繁与困难,理解如何应用以及应用场景即可
一、概论介绍
- 最大匹配:在二分图中最多能找到多少条没有公共端点的边(配对)
示例:
不难发现,这个二分图的最大匹配是如下(不唯一)
但是最大匹配数为 4
- 下面我们严谨的表述一遍最大匹配:
在 G 的一个子图 M 中,M 的边集中的任意两条边都不依附于同一个顶点,则称 M 是一个匹配
选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数
如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。
- 下面介绍两个基本概念(交替路与增广路)
交替路: 从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路
增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)
二、算法原理
原理: 由增广路的性质,增广路中的匹配边总是比未匹配边多一条,所以如果我们放弃一条增广路中的匹配边,选取未匹配边作为匹配边,则匹配的数量就会增加
匈牙利算法就是在不断寻找增广路,如果找不到增广路,就说明达到了最大匹配
可以数学证明这种算法得到的解即为最大匹配数
这个算法的严谨数学证明是比较难的,这里就不加以赘述了,感兴趣可以结合上学期离散数学的图论知识证明,不需要使用任何定理
举例使用:
起始状态尚未匹配,全部都是非匹配边和非匹配点
任意选中 x1 与任意其中一个点 y1 匹配
选中第二个点 x2,x1 没有已霸占 x2 的任何一个对象,故 x2 与任意一个 y2 匹配即可
选中 x3,发现 x3 的第一对象 y1 已经被 x1 占了,于是找出 x3 出发的的交错路径 x3-y1-x1-y4,把交错路中已在匹配上的边 x1-y1 从匹配中去掉,反而匹配剩余的边 x3-y1,x1-y4,这就是增广路技巧
具体操作中将使用 DFS 深度优先搜索
接着选择 x4,发现没有增广路,于是只好选择 y3
接着选择 x5,发现有增广路:x5-y4-x1-y1-x3-y7,于是变成如下
最后选择 x6,x6 无对象可选,而且没有增广路,于是 x6 没法匹配
此结果即为最大匹配
Code-hxw
typedef struct tagMaxMatch{
int edge[COUNT][COUNT];
bool on_path[COUNT];
int path[COUNT];
int max_match;
}GRAPH_MATCH;
void outputRes(int *path){
for (int i = 0 ; i<COUNT; i++) {
printf("%d****%d\n",i,*(path+i));
}
}
void clearOnPathSign(GRAPH_MATCH *match){
for (int j = 0 ; j < COUNT ; j++) {
match->on_path[j] = false;
}
}
//dfs算法
bool FindAugPath(GRAPH_MATCH *match , int xi){
for (int yj = 0 ; yj < COUNT; yj++) {
if ( match->edge[xi][yj] == 1 && !match->on_path[yj]) {
match->on_path[yj] = true;
if (match->path[yj] == -1 || FindAugPath(match,match->path[yj])) {
match->path[yj] = xi;
return true;
}
}
}
return false;
}
void Hungary_match(GRAPH_MATCH *match){
for (int xi = 0; xi<COUNT ; xi++) {
FindAugPath(match, xi);
clearOnPathSign(match);
}
outputRes(match->path);
}
int main() {
GRAPH_MATCH *graph = (GRAPH_MATCH *)malloc(sizeof(GRAPH_MATCH));
for (int i = 0 ; i < COUNT ; i++) {
for (int j = 0 ; j < COUNT ; j++) {
graph->edge[i][j] = 0;
}
}
graph->edge[0][1] = 1;
graph->edge[0][0] = 1;
graph->edge[1][1] = 1;
graph->edge[1][2] = 1;
graph->edge[2][1] = 1;
graph->edge[2][0] = 1;
graph->edge[3][2] = 1;
//举例
for (int j = 0 ; j < COUNT ; j++) {
graph->path[j] = -1;
graph->on_path[j] = false;
}
Hungary_match(graph);
}
参考学习资料:
**[1]**匈牙利算法(二分图) - 神犇(shenben) - 博客园 (cnblogs.com)
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于