数据结构：二分图以及判定二分图

大家好，欢迎来到IT知识分享网。

二分图（Bipartite Graph）是一种特殊的图，它的顶点集合可以划分为两个不相交的子集，使得每条边都连接这两个子集中的一个顶点和另一个顶点。换句话说，二分图中的所有边都只能在两个不同的子集之间。

染色法判定二分图虽然听起来很难，但实际上是一个很简单的算法，读完此文章，相信大家都很容易掌握。

一、二分图的基本知识

一个图 $G=(V,E)$ 是二分图，当且仅当其顶点集 $V$ 可以分割为两个不相交的子集 $U$ 和 $W$，使得图中的每条边 $e$ 满足 $e$ 连接 $U$ 和 $W$ 中的一个顶点。图 $G$ 是二分图，当且仅当存在一个划分 $(U,W)$ 使得：

1. $U\cup W=V$
2. $U\cap W=\varnothing$
3. $\forall (u,w)\in E,\text{其中 }u\in U\text{ 且 }w\in W$

由定义可知：包含自环的一定不是二分图；重边当作一条边来看即可。

1、特性

1. 没有奇环：一个图是二分图当且仅当它不包含奇数长度的环。也就是说，所有环的长度都是偶数。
2. 两色定理：二分图可以用两种颜色对顶点进行着色，使得每条边的两个端点的颜色不同。这种两种颜色的着色也称为二部着色（Bipartite Coloring）。
   
   

2、图示

一个简单的二分图示例：

 U: {1, 2, 3} W: {4, 5} Edges: {(1, 4), (2, 4), (3, 5)} 1 --- 4 2 --- 4 3 --- 5 

在这个例子中，顶点集 $U$ 是 { 1 , 2 , 3 } \{1, 2, 3\} {
1,2,3}，顶点集 $W$ 是 { 4 , 5 } \{4, 5\} {
4,5}，所有边都连接 $U$ 和 $W$ 中的一个顶点。

3、检查一个图是否为二分图

通常使用染色法（二部着色法）判定二分图，可以使用广度优先搜索BFS或深度优先搜索DFS来检查一个图是否为二分图。通过对图进行着色，如果能用两种颜色对图进行着色，使得相邻顶点颜色不同，那么这个图就是二分图。否则，它不是二分图。

3.1、着色的算法原理和思路

由于我们知道，对于$\forall (u,w)\in E$，则必须有$u$和$w$属于不同的集合，那么相当于必须给$u$和$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; }