简介 二分图又称作二部图，是图论中的一种特殊模型。 最大匹配数 = 最小点覆盖 = 总点数- 最大独立集 = 总点数- 最小路径点覆盖 比如下图： 二分图匹配的话我们可以用到——匈牙利算法，二分图判定的话我们可以直接用BFS，我看有些图是DFS也是一样的道理，就是判断邻边是否颜色相同（重点） 思路 1）我们首先定一个起点，将起点加入队列deque里面，每次bfs取出来顶端的 2）然后对其的所有邻边进行染色（染不同的色） i）情况一：相邻的边没有被染色 那么也就是还没有进入过队列，那么这个时候边染成不同的色，边将其压…