用于二分图匹配的匈牙利算法

二分图匹配问题

二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。（见下图）

如图蓝线所示是一种最大二分匹配方案，匹配数=3
警告：使用IE6浏览会极不正常，不信你把图片下载下来用看图工具看看。

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)

（以上除图片均来自百度百科）

匈牙利算法

先考虑一道题:USACO-4.2.2-stall4

求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。

可以用网络流的最大流实现，不过最大流比较复杂，使用匈牙利算法编程复杂度低。

算法最基本轮廓：

红线代表Find函数的调用,蓝线代表已有的配对

查看或下载GIF版本

样例动画演示

置边集M为空（初始化，谁和谁都没连着）
选择一个新的原点寻找增广路
重复(2)操作直到找不出增广路径为止（2，3步骤构成一个循环）

模拟步骤如右图所示(过于详细，大牛请无视)：

初始化（清空）
从A所连接的点中找到一个未在本次循环中搜索过的点2，并将2标记为搜索过，因为2没有被连接过，匹配A2
结束上次，开始新的循环，将所有点标记为未搜索过
搜索B，找到一个未在本次循环中搜索过的点2，标记为搜索过
发现2被匹配过，从2的父亲A寻找增广路，递归搜索A{从A所连接的点中找到一个未在本次循环中搜索过的点5（1已经标记为绿色），将5标记为搜索过，因为5没有被匹配过，匹配A5}找到增广路（此处为增广路的关键）
结束上次，开始新的循环，将所有点标记为未搜索过
搜索C，找到一个未在本次循环中搜索过的点1，并将1标记为搜索过,发现1未被匹配过，匹配C1
结束上次，开始新的循环，将所有点标记为未搜索过
搜索D，找到一个未在本次循环中搜索过的点1，并将1标记为搜索过，发现1被匹配过，递归搜索1的源C寻找增广路
{搜索C，找到一个未在本次循环中搜索过的点5，标记为搜索过，发现5被匹配，进一步返现没有其他可连接点，返回找不到增广路}返回第9步
搜索D，找到一个未在本次循环中搜索过的点2，发现2被匹配，递归搜索2的源B寻找增广路
{搜索B，找到一个未在本次循环中搜索过的点3，并将3标记为搜索过，发现3未被匹配，匹配B3返回找到}既然B另寻新欢，匹配D2
结束上次，开始新的循环，将所有点标记为未搜索过，递归搜索D寻找增广路
搜索E，找到一个未在本次循环中搜索过的点2，并将2标记为搜索过，发现2被匹配过，递归搜索2的源D寻找增广路
{搜索D，发现1，5均被匹配过，返回找不到增广路}
E无其他可连接节点，放弃E，E后无后续节点，已经遍历A-E，结束算法

附本体题解CODE：

/*
ID:
PROG: stall4
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <memory.h>
#define cin fin
#define cout fout
#define din cin
#define dout cout
using namespace std;
ifstream fin ("stall4.in" );
ofstream fout("stall4.out");
int tab[201][201];//邻接矩阵,不是真正意义的邻接矩阵,第一维对应牛,第二维对应牛棚
int state[201],result[201];//stata:是否被搜索过;result:某牛栏对应的牛
int n,m;
int ans;//找到多少匹配

int find(int x){// 匈牙利算法
    int i;
    for (i=1;i<=m;i++){
        if (tab[x][i]==1 && !state[i]){
           state[i]=1;//标记为搜索过
           if (result[i]==0//未被匹配过
		   || find(result[i])){//能找到一条增广路
              result[i]=x;//匹配i,x
              return 1;//能找到新的匹配
              }
           }
        }
    return 0;
    }
int main(){
    int i,j;
    int n1,t;
    cin >> n >> m;
    memset(tab,0,sizeof(tab));
    for (i=1;i<=n;i++){
        cin >> n1;
        for (j=1;j<=n1;j++){
            cin >> t;
            tab[i][t]=1;
            }
        }
    for (i=1;i<=n;i++){
        memset(state,0,sizeof(state));//清空是否搜索过数组
        if (find(i)) ans++;//找到新的匹配
        }//完成后 Result[i]保存着第i个牛栏对应的奶牛，本题不用输出，其他题有可能用
    cout << ans<< endl;
    //system("pause");
    return 0;
    fin.close();
    fout.close();
    }

ID:

PROG: stall4

LANG: C++

#include <iostream>

#include <fstream>

#include <stdlib.h>

#include <memory.h>

#define cin fin

#define cout fout

#define din cin

#define dout cout

using namespace std;

ifstream fin ("stall4.in" );

ofstream fout("stall4.out");

int tab[201][201];//邻接矩阵,不是真正意义的邻接矩阵,第一维对应牛,第二维对应牛棚

int state[201],result[201];//stata:是否被搜索过;result:某牛栏对应的牛

int n,m;

int ans;//找到多少匹配

int find(int x){// 匈牙利算法

int i;

for (i=1;i<=m;i++){

if (tab[x][i]==1 && !state[i]){

state[i]=1;//标记为搜索过

if (result[i]==0//未被匹配过

|| find(result[i])){//能找到一条增广路

result[i]=x;//匹配i,x

return 1;//能找到新的匹配

}

return 0;

}

int main(){

int i,j;

int n1,t;

cin >> n >> m;

memset(tab,0,sizeof(tab));

for (i=1;i<=n;i++){

cin >> n1;

for (j=1;j<=n1;j++){

cin >> t;

tab[i][t]=1;

}

for (i=1;i<=n;i++){

memset(state,0,sizeof(state));//清空是否搜索过数组

if (find(i)) ans++;//找到新的匹配

}//完成后 Result[i]保存着第i个牛栏对应的奶牛，本题不用输出，其他题有可能用

cout << ans<< endl;

//system("pause");

return 0;

fin.close();

fout.close();

}

另外,最小点集覆盖问题其实相当于二分图最大匹配问题,证明见Matrix67 博客二分图最大匹配的König定理及其证明

例题:POJ3041

原创文章，转载请注明： 转载自Comzyh的博客

本文链接地址: 用于二分图匹配的匈牙利算法

6 replies on “用于二分图匹配的匈牙利算法”

Pingback： Hungarian algorithm | 醉饮春醪
wilbeibi说道：

2015年02月22日 1:54 上午

Really helpful

回复
allan说道：

2015年05月18日 10:10 下午

return 后面再close真的没问题么。。

回复
1. comzyh说道：
  
  2015年06月3日 12:22 上午
  
  显然是有问题的….年代久远的代码…
  
  回复
光说道：

2015年07月27日 11:13 上午

楼主这个图（多结点图和GIF）是什么软件做的，用visio画线段树之类的图好麻烦，也试过一个用代码画图的（Graphviz）但是不好看

回复
1. comzyh说道：
  
  2015年08月6日 11:18 下午
  
  当年是用firework画的，很耗时。graphviz效果拔群～
  
  回复

发表评论取消回复

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。

二分图匹配问题

匈牙利算法

共享此文章：

赞过：

相关

6 replies on “用于二分图匹配的匈牙利算法”

发表评论取消回复