PS:其实不用理解透增广路,交替路,网上有对代码的形象解释,看懂也能做题,下面我尽量把原理说清楚 基本概念 (部分来源.部分来源) 二分图: 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B ),则称图G为一个二分图. 匹配: 一个匹配即一个包含若干条边的集合,且其中任意两条边没有公共端点.下图标红的边即为匹配 最大匹配: 匹配数最大,如下图有4条匹配边 完