阅读量:0
文章目录
二分图（Bipartite Graph）是一种特殊的图，它的顶点集合可以划分为两个不相交的子集，使得每条边都连接这两个子集中的一个顶点和另一个顶点。换句话说，二分图中的所有边都只能在两个不同的子集之间。
染色法判定二分图虽然听起来很难，但实际上是一个很简单的算法，读完此文章，相信大家都很容易掌握。
一、二分图的基本知识
一个图 G = ( V , E ) G = (V, E) G=(V,E) 是二分图，当且仅当其顶点集 V V V 可以分割为两个不相交的子集 U U U 和 W W W，使得图中的每条边 e e e 满足 e e e 连接 U U U 和 W W W 中的一个顶点。图 G G G 是二分图，当且仅当存在一个划分 ( U , W ) (U, W) (U,W) 使得：
- U ∪ W = V U \cup W = V U∪W=V
- U ∩ W = ∅ U \cap W = \emptyset U∩W=∅
- ∀ ( u , w ) ∈ E , 其中 u ∈ U 且 w ∈ W \forall (u, w) \in E, \text{其中 } u \in U \text{ 且 } w \in W ∀(u,w)∈E,其中 u∈U 且 w∈W
由定义可知：包含自环的一定不是二分图；重边当作一条边来看即可。
1、特性
- 没有奇环：一个图是二分图当且仅当它不包含奇数长度的环。也就是说，所有环的长度都是偶数。
- 两色定理：二分图可以用两种颜色对顶点进行着色，使得每条边的两个端点的颜色不同。这种两种颜色的着色也称为
二部着色（Bipartite Coloring）。
2、图示
一个简单的二分图示例：
U: {1, 2, 3} W: {4, 5} Edges: {(1, 4), (2, 4), (3, 5)} 1 --- 4 2 --- 4 3 --- 5 在这个例子中，顶点集 U U U 是 { 1 , 2 , 3 } \{1, 2, 3\} {1,2,3}，顶点集 W W W 是 { 4 , 5 } \{4, 5\} {4,5}，所有边都连接 U U U 和 W W W 中的一个顶点。
3、检查一个图是否为二分图
通常使用染色法（二部着色法）判定二分图，可以使用广度优先搜索BFS或深度优先搜索DFS来检查一个图是否为二分图。通过对图进行着色，如果能用两种颜色对图进行着色，使得相邻顶点颜色不同，那么这个图就是二分图。否则，它不是二分图。
相当于将结点分为两个集合的方法转换成了着色问题。
3.1、着色的算法原理和思路
由于我们知道，对于 ∀ ( u , w ) ∈ E \forall (u, w) \in E ∀(u,w)∈E，则必须有 u u u和 w w w属于不同的集合，那么相当于必须给 u u u和 w w w必须染上不同的颜色。由于二分图只能分为两个集合因此只有有两种颜色，那么我们可以使用普通的遍历方法进行交替着色。相同颜色表示在同一个集合中，它们之间必须没有边。
例如我们将0号结点初始化为红色，从0号结点开始进行遍历，对其相邻结点进行绿色着色，然后使用dfs或bfs遍历策略，再选择其相邻节点进行遍历（注意已经访问过的结点不再次访问），在遍历的过程中，如果相邻结点已经被染色，且染色的颜色和其不一样，则出现错误，因为染过色的结点必然是受到之前遍历过的结点颜色限制的，此时与之前的限制矛盾，则必然不是二分图；如果染色的颜色和其一样，则不再考虑它。直至遍历完所有节点，如果遍历完了所有结点且不存在问题则是二分图。
- 已经访问过的结点不再次访问的原因是：如果访问它，根据算法说明前面的染色都是正确的，再次访问它，它又进行相同的染色，产生了重复，会进入死循环
- 如果染色的颜色和其一样，则不再考虑它的原因是：根据
dfs一个节点一旦被染色则一定被深度遍历，被访问不能再次访问避免重复。根据bfs一个节点一旦被染色则一定被入队列，被入队列的节点即被访问。只有未被染色的结点才是从未被访问的结点。
可以发现，不连通图的多个连通分量，分别是二分图就行。一个顶点的图必然是二分图。
交替染色方法：
将颜色标记为0和1，未染色标记为-1，使用异或进行交替染色如下：
w_color = u_color ^ 1;//值得注意的是^运算 比 ==运算的优先级还低 如果u的颜色是0则异或为1，如是1则异或为0。
使用的数据结构：
除了存储图之外，我们最好使用一个数组来存储各个顶点的颜色，以便于对不同连通分量进行访问。
3.2、算法示例：使用 BFS 检查二分图
#include <bits/stdc++.h> using namespace std; bool bfs(const vector<vector<int>>& graph, int start, vector<int>& color) { queue<int> q; q.push(start); color[start] = 0; while (!q.empty()) { int node = q.front(); q.pop(); for (int neighbor : graph[node]) { if (color[neighbor] == -1) { color[neighbor] = color[node] ^ 1; // 着不同的颜色 q.push(neighbor); } else if (color[neighbor] == color[node]) { return false; // 相邻节点颜色相同，不是二分图 } } } return true; } bool isBipartite(const vector<vector<int>>& graph) { int n = graph.size(); vector<int> color(n, -1); for (int i = 0; i < n; ++i) { if (color[i] == -1) { if (!bfs(graph, i, color)) { return false; } } } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int>> graph(n); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u; --v; // 将节点编号调整为从 0 开始 graph[u].emplace_back(v); graph[v].emplace_back(u); } if (isBipartite(graph)) { cout << "Yes\n"; } else { cout << "No\n"; } return 0; } 3.3、算法示例：使用 DFS 检查二分图
#include <bits/stdc++.h> using namespace std; vector<int> color; bool dfs(const vector<vector<int>>& graph, int u, int c) { color[u] = c; for (int v : graph[u]) { if (color[v] == -1) { if (!dfs(graph, v, c ^ 1)) { return false; } } else if (color[v] == color[u]) { return false; } } return true; } bool isBipartite(const vector<vector<int>>& graph) { int n = graph.size(); color.assign(n, -1); for (int i = 0; i < n; ++i) { if (color[i] == -1) { if (!dfs(graph, i, 0)) { return false; } } } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int>> graph(n); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u; --v; // 将节点编号调整为从 0 开始 graph[u].emplace_back(v); graph[v].emplace_back(u); } if (isBipartite(graph)) { cout << "Yes\n"; } else { cout << "No\n"; } return 0; } 4、应用
二分图在许多应用中具有重要意义，例如：
- 匹配问题：如二分图最大匹配，用于分配任务或资源。
- 网络流：二分图匹配可以转换为最大流问题。
- 推荐系统：用户与物品的关系图可以建模为二分图。
二、例题
1.LeetCode：785. 判断二分图
读了题干可知，这是一个经典的判定二分图的题目，直接使用基本方法即可。这里使用DFS。
class Solution { public: bool isBipartite(vector<vector<int>>& graph) { color.assign(graph.size(), -1); for(int i = 0; i < graph.size(); ++ i){ if(color[i] == -1){ color[i] = 0; if(!Bfs(graph, i)){ return false; } } } return true; } private: bool Bfs(vector<vector<int>> & graph, int u){ queue<int> q; q.push(u); while(!q.empty()){ int s = q.front();q.pop(); for(auto & v : graph[s]){ if(color[v] == color[s]) return false; if(color[v] == (color[s] ^ 1)) continue; if(color[v] == -1){ color[v] = color[s] ^ 1; if(!Bfs(graph, v)) return false; } } } return true; } vector<int> color; }; 2.Acwing：860. 染色法判定二分图
虽然这个题存在重边和自环，但完全不影响判断。
- 自环也是边，按相同的方式进行着色，会发现一定不是二分图。
- 重边也是边，按相同的方式进行着色，两次判断一个相连顶点不会存在两次颜色不一样，而且因为已经着色的点不会再次被访问也不会出现重复遍历的情况。
这里使用BFS和DFS都行，为了和上题区分，这里使用了DFS：
#include<bits/stdc++.h> using namespace std; class Solution { public: bool isBipartite(vector<vector<int>>& graph) { color.assign(graph.size(), -1); for(int i = 0; i < graph.size(); ++ i){ if(color[i] == -1){ color[i] = 0; if(!dfs(graph, i)){ return false; } } } return true; } private: bool dfs(vector<vector<int>> & graph, int u){ for(auto & v : graph[u]){//u的边集 if(color[v] == color[u]) return false;//相邻顶点和u颜色相同 if(color[v] == (color[u] ^ 1)) continue;//相邻顶点和u颜色不相同，直接结束 if(color[v] == -1){ color[v] = color[u] ^ 1; if(!dfs(graph, v)) return false; } } return true; } vector<int> color; }; int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<vector<int>> graph(n); while(m --){ int u, v; cin >> u >> v; graph[--u].emplace_back(--v); graph[v].emplace_back(u); } Solution Bipartite; if(Bipartite.isBipartite(graph)){ cout << "Yes"; }else cout << "No"; return 0; } 
