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; // 初始颜色为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;}
};