摘要：
二分图的概念：二分图又称作二部图，是图论中的一种特殊模型 二分图的概念：二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
匹配：在图论中，一个匹配是一个边的集合，其中任意两条边都没有公共顶点。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点，则这条交替路称为增广路。
增广路有个重要特点就是：未匹配边数比匹配边数多一，这样就可以让未匹配边和匹配边身份交换使得匹配边数加一，所以一直寻找增广路来增加匹配数，直到找不到增光路为止。
代码实现（Dfs）：
struct Edge{ int from； int to;};vector G[max];//存储i点的出发点编号int matchingnode[max];int check[max];int Dfs(int u){ vector ::iterator it; for(it=G[u].begin();it!=G[u].end();it++) { int v=*it; if(!check[v])//判断是否在交替路中 { check[v]=1; if(matchingnode[v]==-1||Dfs(matchingnode[v]))//是否是匹配点 { matching[v]=u; matching[u]=v; return 1; } } } return 0;}int hungarian (){ int _count; memset(matchingnode,-1,sizeof(matchingnode)); for(int i=0;i 版权声明：本文内容由互联网用户自发贡献，版权归作者所有，本社区不拥有所有权，也不承担相关法律责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件至： 进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容。
用云栖社区APP，舒服~