首页 > 代码库 > #图# #二分图匹配# #匈牙利算法#

#图# #二分图匹配# #匈牙利算法#

二分图

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

区别二分图,关键是看点集是否能分成两个独立的点集。

    技术分享

二分图匹配(匈牙利算法)

  1. 最大匹配:设技术分享 是一个无向图。如顶点集V可分割为两个互不相交的子集技术分享 ,选择这样的子集中边数最大的子集称为图的最大匹配问题(maximal matching problem)。
  2. 完全匹配:如果一个匹配中, 技术分享 且匹配数 技术分享 ,则称此匹配为完全匹配,也称作完备匹配。
  3. 完美匹配:如果一个匹配中, 技术分享 且匹配数 技术分享 ,称为完美匹配(所有的点都匹配

 

 如图:

点集分成数字和字母,给定边的关系,求最大匹配。

 技术分享

(1)从数字点集开始遍历,从1号开始,所连边终点未被标记-->标记,进行下一个点;已被标记过-->搜索下一条边。

技术分享

(2)3号只有一条边,且A已被标记过(3委屈)。匈牙利算法就要做一些magic的事情了,从3号搜索到A,因为A已被标记过,直接到2。(红色边为深搜所得边)

技术分享

(3)从2深搜到C;C也被标记过,直接到1。

技术分享

(4)1搜索到E,且E未被标记。

技术分享

(5)此时,将以上红色&蓝色都有的边删除标记,只有红色的边 为匹配边。

技术分享

(6)这样1,2,3号点就处理完了,以此类推处理完整张图。

技术分享

在(2)(3)(4)过程中,我们可以发现,从3号(未被标记过)开始每次遍历的边都遵循着 未匹配->已匹配->未匹配->已匹配... 的规律,此时走过的路为增广路

而对走过的增广路取反,所得到的匹配边由原先的n条变为(n+1)条。(将M和P进行取反操作可以得到一个更大的匹配技术分享 。)

当我们对数字点集全部操作完就已求出最大匹配(不必再对字母点集操作,因为已通过边便利过可遍历的字母点集)。

/*

增广路

若P是图G中一条连通两个未匹配顶点的路径,并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径(举例来说,有A、B集合,增广路由A中一个点通向B中一个点,再由B中这个点通向A中一个点……交替进行)。

由增广路的定义可以推出下述五个结论:
1-P的路径个数必定为奇数,第一条边和最后一条边都不属于M。
2-不断寻找增广路可以得到一个更大的匹配M’,直到找不到更多的增广路。
3-M为G的最大匹配当且仅当不存在M的增广路径。
4-最大匹配数M+最大独立数N=总的结点数
5 -- 二分图的最小路径覆盖数 = 原图点数 - 最大匹配数

*/

 

 1 //二分图匹配(匈牙利算法的DFS实现)
 2 //初始化:g[][]两边顶点的划分情况
 3 //建立g[i][j]表示i->j的有向边就可以了,是左边向右边的匹配
 4 //g没有边相连则初始化为0
 5 //uN是匹配左边的顶点数,vN是匹配右边的顶点数
 6 //调用:res=hungary();输出最大匹配数
 7 //优点:适用于稠密图,DFS找增广路,实现简洁易于理解
 8 //时间复杂度:O(VE)
 9 //***************************************************************************/
10 //顶点编号从0开始的
11 const int MAXN=510;
12 int uN,vN;//u,v数目
13 int g[MAXN][MAXN];
14 int linker[MAXN];
15 bool used[MAXN];
16 bool dfs(int u)//从左边开始找增广路径
17 {
18     int v;
19     for(v=0;v<vN;v++)//这个顶点编号从0开始,若要从1开始需要修改
20       if(g[u][v]&&!used[v])
21       {
22           used[v]=true;
23           if(linker[v]==-1||dfs(linker[v]))
24           {//找增广路,反向
25               linker[v]=u;
26               return true;
27           }
28       }
29     return false;//这个不要忘了,经常忘记这句
30 }
31 int hungary()
32 {
33     int res=0;
34     int u;
35     memset(linker,-1,sizeof(linker));
36     for(u=0;u<uN;u++)
37     {
38         memset(used,0,sizeof(used));
39         if(dfs(u)) res++;
40     }
41     return res;
42 }

 

#图# #二分图匹配# #匈牙利算法#