CC++ & Algorithm

二分图判定

极难2
语言版本：C++
概述：二分图就像把一群朋友分成两队，让所有朋友关系都发生在两队之间，没有队伍内部的朋友关系。我们可以用染色法来检查一个图是不是二分图。

二分图判定：用染色法巧分队伍

你有没有遇到过这样的情境？班级要举行拔河比赛，老师想把全班同学分成红蓝两队，并且要求每一对好朋友都不能分在同一队（因为他们在一起会聊天，不好好比赛）。如果每个同学都只和自己的朋友“对立”，你能否找到一种方案，把所有人分成两队，使得每对好朋友都恰好在不同队伍？如果存在这样的分法，这张“朋友关系图”就是二分图。

什么是二分图？

在数学上，二分图（Bipartite Graph）是这样一种图：我们可以把所有的顶点涂成两种颜色（比如红色和蓝色），并且每条边连接的两个顶点颜色都不同。换句话说，图里的所有边都“跨越”两个颜色集合，没有任何一条边连接同色的顶点。

生活中的例子

  • 分组活动：夏令营把小朋友分成两个小组做任务，有矛盾的小朋友必须分在不同组。如果能成功分组，这个矛盾关系图就是二分图。
  • 比赛安排：乒乓球循环赛中，每场比赛由两名选手参加，我们可以把选手分成两个“半区”，同一半区的人不会互相比赛（除非决赛）。实际上，如果比赛安排是合理的“淘汰赛”，比赛关系图往往就是一棵二叉树，而二叉树是二分图。
  • 男女配对：在一个舞会上，男生只和女生跳舞，那么男生和女生之间的“跳舞关系”就构成二分图（因为男生之间不跳舞，女生之间也不跳舞）。

二分图的重要性质

二分图不包含奇数长度的环。也就是说，如果你在图中找到一个环，而且这个环上的顶点数是奇数（比如3、5、7），那这个图一定不是二分图。因为奇数环需要交替涂色，最后你会发现第一个和最后一个颜色冲突。这个性质也可以用来判断二分图。

如何判定一张图是不是二分图？

最经典的方法就是染色法。染色法就像用两种颜色给地图上的区域涂色，相邻区域颜色不同。我们从任意一个顶点开始，把它涂成颜色0，然后把它的所有邻居都涂成颜色1；紧接着，这些颜色1的邻居又涂成颜色0……这样一层层进行下去。如果碰到一个顶点已经被涂过色，但即将涂的颜色和它当前颜色不同（矛盾），那么就不是二分图。如果整个图都涂完了，没有任何矛盾，就是二分图。

染色法可以用**广度优先搜索（BFS）或深度优先搜索（DFS）**来实现。下面分别介绍两种方式。

用BFS染色（广度优先）

BFS就像“一波一波地传染”——从起点开始，把和它相邻的一圈染成相反颜色，然后再处理下一圈。

代码实现（C++）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 判断图是否为二分图，graph是邻接表，n是顶点个数
bool isBipartiteBFS(const vector<vector<int>>& graph, int n) {
    vector<int> color(n, -1);   // 颜色数组，-1表示未染色，0和1代表两种颜色
    queue<int> q;               // BFS队列

    // 图可能不连通，要遍历每个顶点作为起点
    for (int start = 0; start < n; start++) {
        if (color[start] != -1) continue;   // 已经染过色的顶点跳过（属于前面的连通分量）
        // 从start开始一个新的连通分量，染成颜色0
        color[start] = 0;
        q.push(start);
        
        while (!q.empty()) {
            int u = q.front();   // 当前顶点
            q.pop();
            for (int v : graph[u]) {   // 遍历所有邻居
                if (color[v] == -1) {
                    // 邻居没染色，染成与u不同的颜色（1 - color[u]）
                    color[v] = 1 - color[u];
                    q.push(v);
                } else if (color[v] == color[u]) {
                    // 邻居和当前顶点颜色相同，违反二分图条件，返回false
                    return false;
                }
            }
        }
    }
    // 所有连通分量都染色成功，是二分图
    return true;
}

int main() {
    // 示例：5个顶点 (0~4)，边如下
    int n = 5;
    vector<vector<int>> graph(n);
    // 添加无向边：0-1, 0-2, 1-3, 2-3, 3-4
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(0);
    graph[1].push_back(3);
    graph[2].push_back(0);
    graph[2].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(2);
    graph[3].push_back(4);
    graph[4].push_back(3);

    if (isBipartiteBFS(graph, n)) {
        cout << "这个图是二分图！" << endl;
    } else {
        cout << "不是二分图！" << endl;
    }

    return 0;
}

代码解释：

  • color数组记录每个顶点的颜色（0或1），-1表示还没染色。
  • 因为图可能不连通，所以外层for循环遍历所有顶点，如果某个顶点还没染色，就以它为起点开始新一轮BFS。这保证了所有连通分量都被检查到。
  • 在BFS过程中，遇到邻居v：如果未染色，就染成与当前顶点u相反的颜色（1 - color[u]）；如果已染色，检查是否和u相同——相同就说明矛盾，直接返回false。
  • 如果所有顶点都顺利染色，返回true。

用DFS染色（深度优先）

DFS就像“一条路走到黑”——沿着一条路径一直染下去，遇到分叉再回头。DFS的实现可以递归或非递归，这里用递归方式更简洁。

DFS代码

#include <iostream>
#include <vector>
using namespace std;

// 深度优先染色函数，返回是否成功
bool dfs(int u, int c, const vector<vector<int>>& graph, vector<int>& color) {
    color[u] = c;   // 将当前顶点染成颜色c
    for (int v : graph[u]) {
        if (color[v] == -1) {
            // 邻居未染色，递归染成相反颜色（1-c），如果返回false则直接失败
            if (!dfs(v, 1 - c, graph, color)) return false;
        } else if (color[v] == c) {
            // 邻居颜色相同，矛盾
            return false;
        }
    }
    return true;
}

bool isBipartiteDFS(const vector<vector<int>>& graph, int n) {
    vector<int> color(n, -1);
    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            // 从i开始，染成颜色0
            if (!dfs(i, 0, graph, color)) return false;
        }
    }
    return true;
}

DFS与BFS比较：两种方法本质相同，都是染色法。BFS用队列，更容易想象“一层层扩散”；DFS用递归或栈，代码可能更短。实际使用中，对于稀疏图两者效率差不多，BFS不容易栈溢出（DFS递归深度大时可能爆栈）。

常见错误与注意事项

1. 忘记检查图不连通

很多新手只从顶点0开始BFS/DFS，如果图不连通，其他连通分量就没人管了。比如一个图有两个分开的部分，每个部分都是二分图，但只从0开始，只能染一个部分，另一个部分没被染色，返回true是错的。必须对每个未染色的顶点都启动一次遍历。

2. 自环（自己连自己）

如果一个顶点有一条边连向自己，那它必须和自己不同色，显然不可能。因此含有自环的图一定不是二分图。代码中：if (color[v] == color[u]) 中如果 v == u，会检测到矛盾，所以自动处理。

3. 重边（多条平行边）

多条边连接同一对顶点，不影响判断，只要两个顶点不同色即可。代码中重复检查邻居，不会导致问题。

4. 邻接表方向

二分图是无向图判定，所以添加边时一定要双向添加（如上代码）。如果只添加了单向，图的性质就变了。

5. 染色顺序

染色法从不同起点开始，可能会得到不同的颜色分配，但不影响是否二分图的结论。

完整示例：判断一个比赛分组是否可行

假设有6位同学，他们的朋友关系（必须分在不同队）如下：

1-2, 1-3, 2-4, 3-4, 4-5, 5-6

我们来用代码判断这张图是不是二分图。

主程序

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 这里使用BFS版本
bool isBipartite(const vector<vector<int>>& graph, int n);

int main() {
    int n = 6;   // 同学编号 0~5，方便代码，这里用0对应同学1
    vector<vector<int>> graph(n);
    // 添加双向边
    graph[0].push_back(1);  // 1-2
    graph[1].push_back(0);
    graph[0].push_back(2);  // 1-3
    graph[2].push_back(0);
    graph[1].push_back(3);  // 2-4
    graph[3].push_back(1);
    graph[2].push_back(3);  // 3-4
    graph[3].push_back(2);
    graph[3].push_back(4);  // 4-5
    graph[4].push_back(3);
    graph[4].push_back(5);  // 5-6
    graph[5].push_back(4);

    if (isBipartite(graph, n)) {
        cout << "可以分成两队！" << endl;
    } else {
        cout << "不行，有冲突！" << endl;
    }
    return 0;
}

运行结果：这个图是二分图（因为可以染色成功）。

总结

二分图判定是图论中的基础问题，染色法就像“给邻居涂相反颜色”一样直观。学会了染色法，你就能解决很多实际问题，比如：

  • 安排考试座位：相邻座位不能坐同一个班级的同学（不同班级同学之间可能认识，但这里是为了防止作弊，通常要求同班同学不相邻，但二分图要求所有边连接不同颜色，类似一个班级分到两个考场）。
  • 黑白格涂色：棋盘格的相邻格子不同色，其实就是二分图。
  • 更多图论算法的基础：比如二分图最大匹配（匈牙利算法）需要先判断图是否为二分图；最小点覆盖、最大独立集等问题也依赖于二分图性质。

如果你对二分图的应用感兴趣，可以继续学习：

  • 匈牙利算法：求二分图的最大匹配（比如男女生搭配最多能配成多少对）。
  • 二分图的判定与着色：掌握染色法后，可以尝试用DFS或BFS解决LeetCode上的“判断二分图”题目。
  • 带权二分图：比如每个匹配有不同分值，用KM算法求最大权匹配。

记住：二分图的核心就是“两种颜色能顶点分开，所有边跨颜色”。只要抓住这个本质，染色法永远好用！

例题精讲

1单选题

一个无向图是二分图的充要条件是？

A图中不存在奇环
B图中不存在偶环
C图是连通的
D所有顶点度数均为偶数
2判断题

使用BFS染色法判定二分图时，如果发现相邻节点颜色相同，则该图不是二分图。

3填空题
以下代码用DFS染色法判断二分图，请在___处填入正确条件。
bool dfs(int u, int c) {
    color[u] = c;
    for (int v : adj[u]) {
        if (color[v] == -1) {
            if (!dfs(v, 1 - c)) return false;
        } else if (___) {
            return false;
        }
    }
    return true;
}
4单选题

使用BFS或DFS染色法判定二分图的时间复杂度为（假设图有V个顶点，E条边）？

AO(V)
BO(E)
CO(V+E)
DO(V*E)
5判断题

如果一个无向图是二分图，那么它的所有环的长度都是偶数。