【图论】二分图
二分图,即可以将图中的所有顶点分层两个点集,每个点集内部没有边
判定图为二分图的充要条件:有向连通图不含奇数环
1、染色法
可以解决二分图判断的问题
步骤与基本思路
遍历图中每一个点,若该点未被染色,则遍历该点所相邻的点,相邻的点中未被染色的进行染色操作,已被染色的判断颜色是否合法,合法继续遍历,不合法退出
染色法板子
bool flag = true; |
2、匈牙利算法
可以解决最大匹配数的问题,也就是二分图的两个点集可以连多少条一一对应的边
步骤与基本思路
(1)遍历第一个点集的所有点,每个点遍历之前要记得把第二个点集的状态清空
(2)依次遍历这些点相邻的点,若该点未被遍历过,则判断该点是否满足未与前面的点匹配过或前面与它匹配的点有其他的匹配方案,若满足任意条件则让现在的两点匹配,不满足则说明当前第一个点集的这个点没有匹配对象
匈牙利算法板子
for (int i = 1; i <= n1; i ++ ) |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Texcavator 的秘密基地!
评论