匈牙利算法

不惟一。扩张的顺序不同，枚举顶点的顺序不同，解就不一定相同

好像不应该使用匈牙利，求最优匹配应该使用KM算法。

一般网上下下来的代码，我都要自己看一遍，理解了，确定无误了再把放到自己的toolbox里备用，直接用容易错。

V1,V2是两个点集.其实匈牙利的本质就找用增广路.所谓增广路,其实是这样一种路径:这条路径的起点和终点所连的边为虚边,而其余每一个点连的两条边都是一虚一实.实边是已匹配边,虚边是可以匹配但未匹配的边.A ... B --- C ... D这就是一条增广路.找到增广路之后,只需要把其中的实边变成虚边,虚边变成实边,就可以实现找到新的一个匹配.A ... B --- C ... D => A --- B ... C --- D

哈哈，楼上的回答笑死我了……还有，匈牙利算法的条件好像是要求最小值哦~

其实匈牙利算法就是一种反复尝试的办法，假如换成人的话，就是一条条路试过去看可不可以增广的土办法。所以每次找增广路的时候，我们肯定不会找当次已经找过的路，那就意味着走回头路。而当我们找下条增广路的时候，上次怎么走的路径已经和我们无关了。所以要把标记清零。

适宜解决 生产人员指派问题，人员分配问题。

可以转换为网络流……

匈牙利算法和最小元素法的区别运筹学里解决运输调度问题是有最小元素法和匈牙利算法，感觉它们似乎很相似，都是在矩阵某行或某列减去一个数。请问这两种方法有什么区别？

从解的形式上看，指派问题是一种整数规划问题，但从算法思想看，把它归为运输问题的一种特殊形式更为合适。指派问题是运筹学中一个具有理论意义又很有实用价值的问题，其一般提法是：设有n个人，需要分派他们去做n件工作，由于每个人的专长不同，各人做任一种工作的效率可能不同，因而创造的价值也不同，应如何安排，才能使创造的总价值最大?

匈牙利算法是图论中完成二分图匹配的经典算法之一.输入排队的Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量为目的.因而在调度算法理论研究中应用了二分图最大匹配的Maximum Size Matching(MSM)和 Maximum Weight Matching(MWM)算法成为各种调度算法性能的评价标准.文中介绍了匈牙利算法在输入排队调度算法仿真中的应用,并且得出相应典型算法的性能仿真曲线,从而为进一步研究调度算法打下理论基础.

化简之后的矩阵执行第三步，发现只要5条线就能划掉所有0，小于行列数6，需要执行第4步反复执行两次后，会得到满足大于等于6的行列式，然后从最后两列随便挑个0开始就行了。但是此时每行每列也的确有两个以上的0，原因是你的行上每两行都是相同的如果转换成实际问题，也就是6个人，每两个人做事耗时完全相同，那么他们可以执行的任务就是完全相同的，所以12，34，56，行0的所在列肯定相同（每列不少于一个0）。拿第1行举例，既然1和2可执行任务相同，那么至少需要两列为0（每行不少于一个0）。所以这个行列数转换到最后一定是每行每列两个0。

由B2可得出结论：1——2（也就是说第一个人对应第二项任务）2——1（同理）3——3（同理）4——4（同理）写成置换形式就是最下面那个2乘4矩阵

//二分图最佳匹配,kuhn munkras算法,邻接阵形式,复杂度O(m*m*n)//返回最佳匹配值,传入二分图大小m,n和邻接阵mat,表示权值//match1,match2返回一个最佳匹配,未匹配顶点match值为-1//一定注意m<=n,否则循环无法终止//最小权匹配可将权值取相反数#include <string.h>#define MAXN 310#define inf 1000000000#define _clr(x) memset(x,0xff,sizeof(int)*n)int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){ int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k; for (i=0;i<m;i++) for (l1[i]=-inf,j=0;j<n;j++) l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i]; for (i=0;i<n;l2[i++]=0); for (_clr(match1),_clr(match2),i=0;i<m;i++){ for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++) for (k=s[p],j=0;j<n&&match1[i]<0;j++) if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){ s[++q]=match2[j],t[j]=k; if (s[q]<0) for (p=j;p>=0;j=p) match2[j]=k=t[j],p=match1[k],match1[k]=j; } if (match1[i]<0){ for (i--,p=inf,k=0;k<=q;k++) for (j=0;j<n;j++) if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p) p=l1[s[k]]+l2[j]-mat[s[k]][j]; for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++); for (k=0;k<=q;l1[s[k++]]-=p); } } for (i=0;i<m;i++) ret+=mat[i][match1[i]]; return ret;}

设G=(V,E）是一个无向图。如顶点集V可分割为两个互不相交的子集V1,V2选择这样的子集中边数最大的子集称为图的最大匹配问题（maximal matching problem)如果一个匹配中，|V1|<=|V2|且匹配数|M|=|V1|则称此匹配为完全匹配，也称作完备匹配。特别的当|V1|=|V2|称为完美匹配。在介绍匈牙利算法之前还是先提一下几个概念，下面M是G的一个匹配。M-交错路：p是G的一条通路，如果p中的边为属于M中的边与不属于M但属于G中的边交替出现，则称p是一条M-交错路。如：路径（X3,Y2,X1,Y4），（Y1,X2,Y3）。M-饱和点：对于v∈V(G），如果v与M中的某条边关联，则称v是M-饱和点，否则称v是非M-饱和点。如X1，X2，Y1，Y2都属于M-饱和点，而其它点都属于非M-饱和点。M-可增广路：p是一条M-交错路，如果p的起点和终点都是非M-饱和点，则称p为M-可增广路。如（X3,Y2,X1,Y4）。（不要和流网络中的增广路径弄混了）求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的时间复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。下面介绍用增广路求最大匹配的方法（称作匈牙利算法，匈牙利数学家Edmonds于1965年提出）。增广路的定义（也称增广轨或交错轨）：若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边（即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。由增广路的定义可以推出下述三个结论：1－P的路径个数必定为奇数，第一条边和最后一条边都不属于M。2－将M和P进行取反操作可以得到一个更大的匹配M"。3－M为G的最大匹配当且仅当不存在M的增广路径。算法轮廓：⑴置M为空⑵找出一条增广路径P，通过异或操作获得更大的匹配M"代替M⑶重复⑵操作直到找不出增广路径为止

什么来的

是所谓的匈牙利法吗，如果是，那么就是整数规划中0-1规划的分配问题的求解方法，比方四个任务分配给4个人，每人一种，可以得到最大效益

求最大匹配的一种算法，匈牙利数学家Edmonds于1965年提出.

谈匈牙利算法自然避不开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中对应元素为true。 1. 寻找up中一个未盖点 。 2. 从该未盖点出发 ，搜索一条可行的路线 ，即由细边出发， 由细边结束， 且细粗交错的路线 。 3. 若找到 ，则修改该路线上的点所对应的over1，over2，use的元素。重复步骤1。 4. 统计use中已覆盖的边的条数total，总数n减去total即为问题的解。

谈匈牙利算法自然避不开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中对应元素为true。 1. 寻找up中一个未盖点 。 2. 从该未盖点出发 ，搜索一条可行的路线 ，即由细边出发， 由细边结束， 且细粗交错的路线 。 3. 若找到 ，则修改该路线上的点所对应的over1，over2，use的元素。重复步骤1。 4. 统计use中已覆盖的边的条数total，总数n减去total即为问题的解。

我们根据机器学习的定义（即让计算机不依赖确定的编码指令来自主的学习工作）可知，匈牙利算法的整个求解过程是确定性的，即一张图下进行求解，运行n次，算法流程以及结果都不具备不确定性。因此，匈牙利算法并非机器学习算法。

设G=(V,E）是一个无向图。如顶点集V可分割为两个互不相交的子集V1,V2选择这样的子集中边数最大的子集称为图的最大匹配问题（maximal matching problem)如果一个匹配中，|V1|<=|V2|且匹配数|M|=|V1|则称此匹配为完全匹配，也称作完备匹配。特别的当|V1|=|V2|称为完美匹配。

匈牙利算法的本质是利用增广路径来调整匹配，使得匹配数最大。在算法的执行过程中，我们对于每个点都会记录其相应的等价增量。本算法的核心思想是寻找增广路径，由于增广路径上的点交替属于匹配点和未匹配点，所以对相应的等价增量进行了修改，即对左部未匹配点的等价增量加上 d，对右部已匹配点的等价增量减去 d。由于每次修改后两部分等价增量的和不变，因此系数矩阵减去常数的最优解不会发生变化。

对于一个点x和一个点i，如果x和i匹配，那么就匹配；如果i已和j匹配，那么就看j能否和别的点匹配，如果能就可以x和i匹配，匹配数+1。

匈牙利算法的步骤1.将关联矩阵每一行减去本行的最小值,进入步骤二。2.将新的矩阵每一列减去本列的最小值,进入步骤三。3.用最少的行线和列线将新矩阵中的零全部穿起来,检查目前是否为最优分配。如果行线和列线没有将...4.将行线和列线没有穿起来的元素中找到最小元素,将剩余元素减去最小元素,对应行线

原址： https://blog.csdn.net/siss0siss/article/details/51325656 资料写的不完善，本篇文章较详细友善。 匈牙利解法： 过程 一、做减法（归约）： 行归约：每行元素减去该行最小元素。 列归约：每行元素减去该行最小元素。 归约顺序无所谓，目的就是把所有的数尽可能化的很小，但最小的数不能为负数 二、圈零划零 找到含零元素最少的行，对零元素打圈，划去打圈零元素所在行和列存在的零元素，重复这个步骤，直到矩阵中所有的零元素都被处理完。 三、打勾划线 四、调整量的加减

格式说明输入格式：第1行3个整数，V1,V2的节点数目n1,n2,G的边数m第2-m+1行，每行两个整数t1,t2，代表V1中编号为t1的点和V2中编号为t2的点之间有边相连输出格式：1个整数ans，代表最大匹配数邻接矩阵-C #include<stdio.h>#include<string.h>intn1, n2, m, ans;int result[101];//记录V2中的点匹配的点的编号bool state[101];//记录V2中的每个点是否被搜索过bool data[101][101];//邻接矩阵true代表有边相连void init(){    int t1, t2;    memset(data, 0, sizeof(data));    memset(result, 0, sizeof(result));    ans = 0;    scanf(%d%d%d, &n1, &n2, &m);    for(int i = 1; i <= m; i++)    {        scanf(%d%d, &t1, &t2);        data[t1][t2] = true;    }    return;}bool find(inta){    for(int i = 1; i <= n2; i++)    {        if(data[a][i] == 1 && !state[i]) //如果节点i与a相邻并且未被查找过        {            state[i] = true; //标记i为已查找过            if(result[i] == 0 //如果i未在前一个匹配M中                || find(result[i])) //i在匹配M中，但是从与i相邻的节点出发可以有增广路            {                result[i] = a; //记录查找成功记录                                result[a]  =  i;                returntrue;//返回查找成功            }        }    }    return false;}int main(){    init();    for(int i = 1; i <= n1; i++)    {        memset(state, 0, sizeof(state)); //清空上次搜索时的标记        if(find(i))        {            ans++;    //从节点i尝试扩展        }    }    printf(%d , ans);    return 0;}邻接矩阵-pascal Programhungary;Constmax=100;Vardata:array[1..max,1..max]ofboolean;{邻接矩阵}result:array[1..max]ofinteger;{记录当前连接方式}state:array[1..max]ofboolean;{记录是否遍历过，防止死循环}m,n1,n2,i,t1,t2,ans:integer;Functiondfs(p:integer):boolean;vari:integer;beginfori:=1ton2doifdata[p,i]andnot(state[i])then{有边存在且没有被搜索过}beginstate[i]:=true;if(result[i]=0)ordfs(result[i])then{没有被连过或寻找到增广路}beginresult[i]:=p;exit(true);end;end;exit(false);end;beginreadln(n1,n2,m);fillchar(data,sizeof(data),0);fori:=1tomdobeginreadln(t1,t2）；data[t1,t2]:=true;end;fillchar(result,sizeof(result),0);ans:=0;fori:=1ton1dobeginfillchar(state,sizeof(state),0);ifdfs(i)theninc(ans);end;writeln(ans);end.邻接表-C++ #include<iostream>#include<cstring>usingnamespacestd;//定义链表structlink{intdata;//存放数据link*next;//指向下一个节点link(int=0);};link::link(intn){data=n;next=NULL;}intn1,n2,m,ans=0;intresult[101];//记录n1中的点匹配的点的编号boolstate[101];//记录n1中的每个点是否被搜索过link*head[101];//记录n2中的点的邻接节点link*last[101];//邻接表的终止位置记录//判断能否找到从节点n开始的增广路boolfind(constintn){link*t=head[n];while(t!=NULL){//n仍有未查找的邻接节点时if(!(state[t->data])){//如果邻接点t->data未被查找过state[t->data]=true;//标记t->data为已经被找过if((result[t->data]==0)||//如果t->data不属于前一个匹配M(find(result[t->data]))){//如果t->data匹配到的节点可以寻找到增广路result[t->data]=n;//那么可以更新匹配M"，其中n1中的点t->data匹配nreturntrue;//返回匹配成功的标志}}t=t->next;//继续查找下一个n的邻接节点}returnfalse;}intmain(){intt1=0,t2=0;cin>>n1>>n2>>m;for(inti=0;i<m;i++){cin>>t1>>t2;if(last[t1]==NULL)last[t1]=head[t1]=newlink(t2);elselast[t1]=last[t1]->next=newlink(t2）；}for(inti=1;i<=n1;i++){memset(state,0,sizeof(state));if(find(i))ans++;}cout<<ans<<endl;return0;}邻接矩阵-C++ #include<iostream>#include<cstring>using namespace std;int map[105][105];int visit[105],flag[105];int n,m;bool dfs(int a){    for(int i=1; i<=n; i++)    {        if(map[a][i]&&!visit[i])        {            visit[i]=1;            if(flag[i]==0||dfs(flag[i]))            {                flag[i]=a;                return true;            }        }    }    return false;}int main(){    while(cin>>n1 >>n2 >>m)    {        memset(map,0,sizeof(map));        for(int i=1; i<=m; i++)        {            int x,y;            cin>>x>>y;            map[x][y]=1;        }        memset(flag,0,sizeof(flag));        int result=0;        for(int i=1; i<=n1; i++)        {            memset(visit,0,sizeof(visit));            if(dfs(i))result++;        }        cout<<result<<endl;    }    return 0;}邻接表-pascal（使用动态链表）（方法基于之前的邻接矩阵-pascal） programhungarian_algorithm;//匈牙利算法typenode=^link;//链表定义link=recordg:longint;//指向节点next:node;end;varn1,n2,m,a,v1,v2,ans:longint;flag:array[1..1000000]ofboolean;//记录在main递归过程中是否已访问过，防止死循环nd:array[1..1000000]ofnode;//邻接表resultt:array[1..1000000]oflongint;//记录v2中节点的最终匹配于v1中的几号节点functionmain(wei:longint):boolean;varp:node;beginp:=nd[wei];whilep<>nildobeginifflag[p^.g]{没有被搜索过}thenbeginflag[p^.g]:=false;if(resultt[p^.g]=0)or(main(resultt[p^.g])){没有被连过或原来指向的节点寻找到新的增广路}thenbeginresultt[p^.g]:=wei;exit(true);end;end;p:=p^.next;end;exit(false)end;procedureaddd(v1,v2:longint);//建立邻接表过程varp:node;beginnew(p);p^.g:=v2;p^.next:=nd[v1];nd[v1]:=p;end;beginreadln(n1,n2,m);fora:=1tomdobeginreadln(v1,v2);addd(v1,v2);end;ans:=0;fillchar(resultt,sizeof(resultt),0);fora:=1ton1dobeginfillchar(flag,sizeof(flag),true);ifmain(a)theninc(ans);end;writeln(ans);fora:=1ton2doifresultt[a]<>0thenwriteln(resultt[a],"---",a);end.

解决二分图的最大匹配问题。

是的。KM是通过巧妙的方法把带权问题归结为不带权问题。

给了C代码，Java还不会？以后别提问了，我都替你不好意思……谢谢……

中国如今男女比例严重失衡，2021年预计将有9200万单身贵族。为了帮助解决这个社会性问题，提升整体人民的幸福感，小K打算投身到这份伟大的事业中。 “ 几何思维 ”婚恋所，用最科学的方法，帮你脱单。通过概率论寻找最佳匹配对象，再通过微积分精确计算好感上升曲线，最后用数值分析无限逼近对方的理想型。最可怕的是，还包邮呢亲，关注一波了解一下？ 上班第一天，老板给了小K一份单身男女好感的数据资料。如下图，连线表示双方互有好感，可以尝试处对象。 突然遇到了一个问题，那怎么才能进行最大的匹配，创造整体人民最大的幸福感呢，当然也可以顺便拿最多的中介费啦。 很多时候不是你比别人差，而是你执行力不够，在犹豫中丧失机会。 大家就先行动起来吧。 快看，男1号选手在小K的鼓励(怂恿)下，率先对女1号发起了进攻。在离失败只有0.01公分的时候，他竟然奇迹般的完成反杀，没错，他成功啦，这种高超的技巧，娴熟的手法简直如同教科书一般，值得在座的每个同学深入研究反复琢磨啊。 男2号选手也不甘落后，也对女2号选手发起了进攻，没错，又一次成功啦。 男3号选手：我勒个去，我上我也行啊。于是也对自己心动的女1号发起了进攻，毫无意外，他阵亡了。。。 中间彩蛋。 男3号不甘心，原地复活，想再战一回。在一个地方跌倒，咱们就换一个地方再跌。。。 于是对女2号发起了进攻。 几经波折。 男3号终于也成为了有牵绊的男人，不论未来有多久，只在乎曾经拥有过。 男4一看：这也没我啥事儿了啊。 以上的过程其实就是经典的 匈牙利算法 ，求解二分图的最大匹配问题。 二分图 定义：设G=(V,E)是一个无向图，顶点集V可分割为两个互不相交的子集X，Y，并且图中每条边关联的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。 判断是否为二分图的充要条件：G至少有两个顶点,且其所有回路的长度均为偶数。 判断方法：染色法 可用bfs或者dfs。 匹配 在二分图G的子图M中，M的边集E中的任意两条边都不依附于同一个顶点，则称M是一个 匹配 。 饱和点 匹配M的边集所关联的点为 饱和点 ，否则为 非饱和点 。如上图： 交错路 定义：图G的一条路径，且路径中的边在属于M和不属于M中交替出现。 增广路(非网络流中的定义) 定义：一条交错路，且该交错路的起点和终点都为匹配M的非饱和点。 如上图，交错路1是增广路；交错路2不是增广路，因为终点 X1 不是非饱和点。 由增广路推出以下结论： 匈牙利算法核心思想： 变量定义及初始化 初始化 递归寻找增广路 遍历所有点 测试数据

匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法。 匈牙利算法是一种组合优化算法，它是解决多项式时间复杂度问题的较快方法。 1.从每一行中找到最小元素，然后从该行的所有元素中减去该值； 2.从每列中找到最小元素，然后从该列中所有元素中减去该值； 3.令m =覆盖表中所有零所需的最小行数； 4. while（m！=覆盖表中所有零所需的最小列数） 从发现的元素中找到最小的元素 从所有其他未发现的元素中减去该元素 将此元素添加到线条相交的元素中 寻找新的 5.使用零来分配可能的组合，即：只要存在零，就可以分配任务； 6.找到最低成本； 7.结束。

匈牙利算法(Edmonds算法)步聚：(1)首先用（*）标记X中所有的非M顶点，然后交替进行步骤（2），（3）。(2)选取一个刚标记（用（*）或在步骤（3）中用（yi）标记）过的X中顶点，例如顶点xi，如果xi与y为同一非匹配边的两端点，且在本步骤中y尚未被标记过,则用（xi）去标记Y中顶点y。重复步骤(2)，直至对刚标记过的X中顶点全部完成一遍上述过程。(3)选取一个刚标记（在步骤(2)中用(xi)标记）过的Y中结点，例如yi，如果yi与x为同一匹配边的两端点，且在本步骤中x尚未被标记过，则用(yi)去标记X中结点x。重复步骤(3)，直至对刚标记过的Y中结点全部完成一遍上述过程。 (2),(3)交替执行，直到下述情况之一出现为止： (I)标记到一个Y中顶点y，它不是M顶点。这时从y出发循标记回溯，直到（*）标记的X中顶点x，我们求得一条交替链。设其长度为2k+1，显然其中k条是匹配边，k+1条是非匹配边。(II)步骤(2)或(3)找不到可标记结点，而又不是情况(I)。 (4)当(2),(3)步骤中断于情况(I)，则将交替链中非匹配边改为匹配边，原匹配边改为非匹配边(从而得到一个比原匹配多一条边的新匹配)，回到步骤(1)，同时消除一切现有标记。(5)对一切可能,(2)和(3)步骤均中断于情况(II),或步骤(1)无可标记结点,算法终止(算法找不到交替链).以上算法说穿了，就是从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过交替出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。