匈牙利算法和KM算法简介.ppt

二分图匹配匈牙利算法和KM算法简介二分图的概念?二分图又称作二部图,是图论中的一种特殊模型。?设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。112233445最大匹配?给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。?选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)?如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。匈牙利算法?求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此,需要寻求一种更加高效的算法。?增广路的定义(也称增广轨或交错轨):?若P是图G中一条连通两个未匹配顶点的路径,并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。匈牙利算法?由增广路的定义可以推出下述三个结论:?1-P的路径长度必定为奇数,第一条边和最后一条边都不属于M。?2-P经过取反操作可以得到一个更大的匹配M’。?3-M为G的最大匹配当且仅当不存在相对于M的增广路径。匈牙利算法?用增广路求最大匹配(称作匈牙利算法,匈牙利数学家Edmonds于1965年提出)?算法轮廓:?(1)置M为空?(2)找出一条增广路径P,通过取反操作获得更大的匹配M’代替M?(3)重复(2)操作直到找不出增广路径为止匈牙利算法?程序清单:?Function find(k:integer):integer;?var st,sf,i,j,t:integer;? queue,father:array[1..100] of integer;?begin? queue[1] := k; st := 1; sf := 1;? fillchar(father,sizeof(father),0);? repeat匈牙利算法?for i:=1 to n do? if (father[i]=0)and(a[queue[st],i]=1) then? begin? if match2[i]<>0 then? begin? inc(sf);? queue[sf] := match2[i];? father[i] := queue[st];? end else匈牙利算法?begin? j := queue[st];? while true do? begin? t := match1[j];? match1[j] := i;? match2[i] := j;? if t = 0 then break;? i := t; j := father[t];匈牙利算法?end;? find := 1;? exit;? end;? end;? inc(st);? until st>sf;? find := 0;?end;