C++二分图

二分图（Bipartite Graph）是一种特殊的图结构，其顶点可以分成两个互不相交的集合，使得每条边的两个顶点分别属于这两个集合。二分图在匹配问题（如任务分配、婚姻匹配）和网络流算法中有重要应用。

---

核心概念

• 定义：图 ( G = (V, E) ) 的顶点集 ( V ) 可划分为两个不相交的子集 ( U ) 和 ( V )，使得每条边的两个端点分别属于 ( U ) 和 ( V )。
• 特性：
  • 图中不包含奇数长度的环。
  • 可以用颜色标记法（如红蓝染色）验证是否为二分图。

---

检测二分图的算法

通过颜色标记法（DFS/BFS遍历染色）判断图是否满足二分性：

算法步骤

1. 选择一个起始顶点，标记为颜色1（如红色）。
2. 遍历其所有相邻顶点，标记为颜色2（如蓝色）。
3. 递归或迭代处理相邻顶点，若发现相邻顶点颜色冲突（相同颜色），则图不是二分图。
4. 对所有未访问的连通分量重复此过程。

---

C++ 模板代码（基于邻接表的DFS实现）

#include <vector>
#include <queue> // 若用BFS需包含此头文件using namespace std;class Solution {
public:bool isBipartite(vector<vector<int>>& graph) {int n = graph.size();vector<int> color(n, -1); // -1表示未染色，0和1表示两种颜色for (int i = 0; i < n; i++) {if (color[i] == -1) { // 处理每个连通分量if (!dfs(graph, color, i, 0)) return false;// 若用BFS：if (!bfs(graph, color, i)) return false;}}return true;}private:// DFS实现bool dfs(vector<vector<int>>& graph, vector<int>& color, int node, int current_color) {if (color[node] != -1) {return color[node] == current_color; // 检查颜色是否冲突}color[node] = current_color;for (int neighbor : graph[node]) {if (!dfs(graph, color, neighbor, 1 - current_color)) return false;}return true;}// BFS实现bool bfs(vector<vector<int>>& graph, vector<int>& color, int start) {queue<int> q;q.push(start);color[start] = 0; // 初始颜色为0while (!q.empty()) {int node = q.front();q.pop();for (int neighbor : graph[node]) {if (color[neighbor] == -1) { // 未染色color[neighbor] = 1 - color[node]; // 染相反颜色q.push(neighbor);} else if (color[neighbor] == color[node]) { // 颜色冲突return false;}}}return true;}
};

---

代码解释

• 邻接表：graph 是邻接表形式，graph[i] 表示顶点 i 的邻居列表。
• 颜色数组：color 记录每个顶点的颜色（-1未染色，0和1为两种颜色）。
• DFS/BFS：
  • DFS递归染色，若发现相邻顶点颜色相同则返回 false。
  • BFS通过队列逐层染色，遇到冲突立即终止。

---

应用场景

1. 匹配问题：如匈牙利算法求二分图的最大匹配。
2. 任务调度：将任务和资源分为两组，边表示可分配关系。
3. 广告推荐：用户和广告分为两组，边表示用户对广告的兴趣。

---

关键点总结

• 时间复杂度：O(V + E)，每个顶点和边被访问一次。
• 空间复杂度：O(V)，用于存储颜色和递归栈（DFS）或队列（BFS）。
• 非连通图处理：需检查所有连通分量。
• 奇数环判定：若存在奇数长度的环，则不是二分图。

---

通过颜色标记法，可以高效判断图是否为二分图，并进一步用于解决更复杂的匹配和分配问题。