匈牙利算法及程序.docx

本文格式为Word版，下载可任意编辑匈牙利算法及程序 匈牙利算法及程序 匈牙利算法自然避不开Hall定理，即是：对于二部图G，存在一个匹配M，使得X的全体顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有： │T(A)│ = │A│ 匈牙利算法是基于Hall定理中充分性证明的思想，其根本步骤为：1．任给初始匹配M；2．若X已饱和那么终止，否那么举行第3步；3．在X中找到一个非饱和顶点x0，作V1 ← {x0}, V2 ← Φ；4．若T(V1) = V2那么由于无法匹配而中断，否那么任选一点y ∈T(V1)\V2；5．若y已饱和那么转6，否那么做一条从x0 →y的可增广道路P，M←M?E(P)，转2；6．由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4；设数组up[1..n] --- 标记二分图的上半片面的点down[1..n] --- 标记二分图的下半片面的点map[1..n，1..n] --- 表示二分图的上，下片面的点的关系True-相连， false---不相连over1[1..n]，over2[1..n] 标记上下片面的已盖点。

use[1..n，1..n] - 表示该条边是否被笼罩 首先对读入数据举行处理 ，对于一条边(x，y) ，起点进集合up，终点进集合down 标记map中对应元素为true1. 探索up中一个未盖点 2. 从该未盖点启程 ，探寻一条可行的路线 ，即由细边启程， 由细边终止， 且细粗交织的路线 3. 若找到 ，那么修改该路线上的点所对应的over1，over2，use的元素重复步骤14. 统计use中已笼罩的边的条数total，总数n减去total即为问题的解匈牙利算法开放分类： 算法、数据布局、离散数学、二分图匹配求最大匹配的一种显而易见的算法是：先找出全部匹配，然后留存匹配数最多的但是这个算法的时间繁杂度为边数的指数级函数因此，需要寻求一种更加高效的算法增广路的定义(也称增广轨或交织轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替展现，那么称P为相对于M的一条增广路径由增广路的定义可以推出下述三个结论：1－P的路径长度必定为奇数，第一条边和结果一条边都不属于M2－P经过取反操作可以得到一个更大的匹配M’3－M为G的最大匹配当且仅当不存在相对于M的增广路径。

用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出)算廓：(1)置M为空(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M(3)重复(2)操作直到找不出增广路径为止时间繁杂度 邻接矩阵：最坏为O(n^3) 邻接表：O(nm)空间繁杂度 O(n^2) O(m+n)程序清单：#includestdio.h#includestring.hbool g[201][201];int n,m,ans;bool b[201];int link[201];bool init(){int _x, 匈牙利算法及程序 _y; memset(g,0,sizeof(g));memset(link,0,sizeof(link));ans=0;if(scanf(%d%d,n,m)==EOF)return false;for(int i=1;i=n;i++){scanf(%d,_x);for(int j=0;j_x;j++){scanf(%d,_y);g[ i ][_y]=true;}}return true;}bool find(int a){for(int i=1;i=m;i++){if(g[a][ i ]==1!b[ i ]){b[ i ]=true;if(link[ i ]==0||find(link[ i ])){link[ i ]=a;return true;}}}return false;}int main(){while(init()){for(int i=1;i=n;i++){memset(b,0,sizeof(b));if(find(i))ans++;}printf(%d\n,ans);}}Pascal:Program matching;Constmax = 1000;Varmap : array [1..max, 1..max] of boolean; {邻接矩阵}match: array [1..max] of integer; {记录当前连接方式}chk : array [1..max] of boolean; {记录是否遍历过，防止死循环}m, n, i, t1, t2, ans: integer;Function dfs(p: integer): boolean;vari, t: integer;beginfor i:=1 to n doif map[p, i] and not chk[ i ] thenbeginchk[ i ] := true;if (match[ i ] = 0) or dfs(match[ i ]) then {没有被连过 或 探索到增广路}beginmatch[ i ] := p;exit(true);end;end;exit(false);end;beginreadln(n, m); {N 为二分图左侧点数 M为可连接的边总数}fillchar(map, sizeof(map), 0);for i:=1 to m dobeginreadln(t1, t2);map[t1, t2] := true;end;fillchar(match, sizeof(match), 0);ans := 0;for i:=1 to n dobeginfillchar(chk, sizeof(chk), 0);if dfs(i) then inc(ans);end;writeln(ans);for i:=1 to 1000 doif match[ i ] 0 thenwriteln(match[ i ], '--', i);end.— 8 —。