C++二分图

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

---

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

---

检测二分图的算法

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

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

---

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; // 初始颜色为0 while (!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通过队列逐层染色，遇到冲突立即终止。

---

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

---

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

---

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