二分图(yhy修改)VIP专享VIP免费

二分图匹配二分图匹配匈牙利算法和匈牙利算法和KMKM算法简介算法简介二分图的概念二分图的概念二分图又称作二部图，是图论中的一种特二分图又称作二部图，是图论中的一种特殊模型。殊模型。设设G=(V,{R})G=(V,{R})是一个无向图。如顶点集是一个无向图。如顶点集VV可分割为两个互不相交的子集，并且图中可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的每条边依附的两个顶点都分属两个不同的子集。则称图子集。则称图GG为二分图。为二分图。112233445最大匹配最大匹配给定一个二分图给定一个二分图GG，在，在GG的一个子图的一个子图MM中，中，MM的边集的边集{E}{E}中的任意两条边都不依附于同中的任意两条边都不依附于同一个顶点，则称一个顶点，则称MM是一个匹配。是一个匹配。选择这样的边数最大的子集称为图的最大匹选择这样的边数最大的子集称为图的最大匹配问题配问题(maximalmatchingproblem)(maximalmatchingproblem)如果一个匹配中，图中的每个顶点都和图中如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也某条边相关联，则称此匹配为完全匹配，也称作完备匹配。称作完备匹配。匈牙利算法匈牙利算法求最大匹配的一种显而易见的算法是：先找求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。此，需要寻求一种更加高效的算法。增广路的定义增广路的定义((也称增广轨或交错轨也称增广轨或交错轨))：：若若PP是图是图GG中一条连通两个未匹配顶点的路中一条连通两个未匹配顶点的路径，并且属径，并且属MM的边和不属的边和不属MM的边的边((即已匹配即已匹配和待匹配的边和待匹配的边))在在PP上交替出现，则称上交替出现，则称PP为为相对于相对于MM的一条增广路径。的一条增广路径。匈牙利算法匈牙利算法由增广路的定义可以推出下述三个结论：由增广路的定义可以推出下述三个结论：11－－PP的路径长度必定为奇数，第一条边和的路径长度必定为奇数，第一条边和最后一条边都不属于最后一条边都不属于MM。。22－－PP经过取反操作可以得到一个更大的匹经过取反操作可以得到一个更大的匹配配M’M’。。33－－MM为为GG的最大匹配当且仅当不存在相对于的最大匹配当且仅当不存在相对于MM的增广路径。的增广路径。匈牙利算法匈牙利算法用增广路求最大匹配用增广路求最大匹配((称作匈牙利算法，匈称作匈牙利算法，匈牙利数学家牙利数学家EdmondsEdmonds于于19651965年提出年提出))算法轮廓：算法轮廓：(1)(1)置置MM为空为空(2)(2)找出一条增广路径找出一条增广路径PP，通过取反操作获，通过取反操作获得更大的匹配得更大的匹配M’M’代替代替MM(3)(3)重复重复(2)(2)操作直到找不出增广路径为止操作直到找不出增广路径为止匈牙利算法匈牙利算法程序清单：程序清单：Functionfind(k:integer):integer;Functionfind(k:integer):integer;varst,sf,i,j,t:integer;varst,sf,i,j,t:integer;queue,father:array[1..100]ofinteger;queue,father:array[1..100]ofinteger;beginbeginqueue[1]:=k;st:=1;sf:=1;queue[1]:=k;st:=1;sf:=1;fillchar(father,sizeof(father),0);fillchar(father,sizeof(father),0);repeatrepeat匈牙利算法匈牙利算法fori:=1tondofori:=1tondoif(father[i]=0)and(a[queue[st],i]=1)thenif(father[i]=0)and(a[queue[st],i]=1)thenbeginbeginifmatch2[i]<>0thenifmatch2[i]<>0thenbeginbegininc(sf);inc(sf);queue[sf]:=match2[i];queue[sf]:=match2[i];father[i]:=queue[st];father[i]:=queue[st];endelseendelse匈牙利算法匈牙利算法beginbeginj:=queue[st];j:=queue[st];whiletruedowhiletruedobeginbegint:=match1[j];t:=match1[j];match1[j]:=i;match1[j]:=i;match2[i]:=j;match2[i]:=j;ift=0thenbreak;ift=0thenbreak;i:=t;j:=father[...