品牌网站建设小蝌蚪,org域名做商业网站,网站开发软件,自动建立wordpress二分图#xff0c;即可以将图中的所有顶点分层两个点集#xff0c;每个点集内部没有边
判定图为二分图的充要条件#xff1a;有向连通图不含奇数环
1、染色法
可以解决二分图判断的问题
步骤与基本思路
遍历图中每一个点#xff0c;若该点未被染色#xff0c;则遍历该…
二分图即可以将图中的所有顶点分层两个点集每个点集内部没有边
判定图为二分图的充要条件有向连通图不含奇数环
1、染色法
可以解决二分图判断的问题
步骤与基本思路
遍历图中每一个点若该点未被染色则遍历该点所相邻的点相邻的点中未被染色的进行染色操作已被染色的判断颜色是否合法合法继续遍历不合法退出
染色法板子
bool flag true;
for (int i 1; i n; i )
{if (!color[i]) // 未被染色则开始遍历{if (!dfs(i, 1)){flag false;break;}}
}bool dfs(int u, int c)
{color[u] c; // 对该点进行染色for (int i h[u]; i ! -1; i ne[i]){int j e[i];if (!color[j]) // 未被染色的点进行染色{if (!dfs(j, 3 - c)) return false;}else if (color[j] c) return false; // 已染色的点判断是否合法}return true;
}
2、匈牙利算法
可以解决最大匹配数的问题也就是二分图的两个点集可以连多少条一一对应的边
步骤与基本思路
1遍历第一个点集的所有点每个点遍历之前要记得把第二个点集的状态清空
2依次遍历这些点相邻的点若该点未被遍历过则判断该点是否满足未与前面的点匹配过或前面与它匹配的点有其他的匹配方案若满足任意条件则让现在的两点匹配不满足则说明当前第一个点集的这个点没有匹配对象
匈牙利算法板子
for (int i 1; i n1; i )
{memset(st, false, sizeof st); // 清空第二个点集的状态if (find(i)) res ;
}bool find(int x)
{for (int i h[x]; i ! -1; i ne[i]){int j e[i];if (!st[j]) // 若该点未被遍历过{st[j] true;// 该点是否满足 未被匹配过 or 匹配的第一个点集的点有其他成功匹配方案if (match[j] 0 || find(match[j])){match[j] x; // 匹配现在的这两点return true;}}}return false;
}
