探索二分图：染色法与匈牙利算法

引言

二分图（Bipartite Graph）是图论中一种特殊的图结构，其顶点集可以划分为两个互不相交的子集，且图中的每条边都连接这两个子集中的顶点。二分图在任务分配、匹配问题、网络流等领域有着广泛的应用。本文将详细介绍二分图的定义、染色法判定二分图的原理、匈牙利算法进行二分图匹配的原理与实现，并通过伪代码帮助读者深入理解。

二分图的定义

1. 二分图的基本概念

二分图：图的顶点集 $V$ 可以划分为两个互不相交的子集 $U$ 和 $V$ ，且图中的每条边都连接 $U$ 和 $V$ 中的顶点。
性质：二分图中不存在奇数长度的环。

2. 二分图的应用场景

任务分配：将任务分配给工人，每个任务只能由一个工人完成。
匹配问题：寻找图中的最大匹配。
网络流：将问题建模为二分图，利用网络流算法求解。

二分图相关术语

二分图

一个图 $G = (V, E)$ 是二分图，如果它的顶点集 $V$ 可以分成两个不相交的子集 $X$ 和 $Y$ ，使得每条边的一个端点属于 $X$ ，另一个端点属于 $Y$ 。

匹配

图中的一个匹配是指一组边的集合，其中任意两条边都没有公共顶点。最大匹配是指包含边数最多的匹配。
下图中所有红色的边表示一个匹配：
在这里插入图片描述

增广路径

一条从非匹配顶点出发，经过若干条交替出现的匹配边和非匹配边，并最终到达另一个非匹配顶点的路径称为增广路径。通过翻转增广路径上的匹配状态（即匹配边变为非匹配边，非匹配边变为匹配边），可以使匹配数量增加1。在下图中，黄色高亮的是增广路径，红色边是已经加入匹配的边。左图高亮的增广路径有3条，长度均为1，右图则高亮了一条长度为3的增广路径。
在这里插入图片描述

染色法判定二分图

1. 算法原理

染色法通过给图的顶点染色来判定图是否为二分图。具体步骤如下：

选择一个起始顶点，将其染成颜色 A。
遍历其邻接顶点，将其染成颜色 B。
递归地对所有顶点进行染色，如果发现某个顶点的邻接顶点颜色与自身相同，则图不是二分图。

2. 正确性证明

充分性：如果图是二分图，则染色法一定可以成功将顶点集划分为两个子集。
必要性：如果染色法成功，则图中不存在奇数长度的环，因此图是二分图。

3. 伪代码

function IsBipartite(Graph):colors = 数组，初始化为 -1for each vertex in Graph:if colors[vertex] == -1:if not BFS(vertex, colors):return Falsereturn Truefunction BFS(start, colors):queue = 队列queue.push(start)colors[start] = 0while queue 不为空:u = queue.pop()for each v in u 的邻接顶点:if colors[v] == -1:colors[v] = 1 - colors[u]queue.push(v)else if colors[v] == colors[u]:return Falsereturn True

代码实现

ACWing 染色法判定二分图

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;const int MAX_NODES = 2e5 + 7;  // 最大节点数// 邻接表表示图的数组
int head[MAX_NODES], nextEdge[MAX_NODES], toNode[MAX_NODES], edgeIndex = 0;
// 颜色数组，用于二分图判定
int nodeColor[MAX_NODES];
int nodeCount, edgeCount;/*** 添加边到邻接表* @param u 起点* @param v 终点*/
void addEdge(int u, int v) {nextEdge[++edgeIndex] = head[u];  // 更新链表指针head[u] = edgeIndex;              // 当前边的索引toNode[edgeIndex] = v;            // 边指向的节点
}/*** 判断是否为二分图* @param startNode 起始节点* @return 是否是二分图*/
bool isBipartiteGraph(int startNode) {queue<int> nodeQueue;nodeQueue.push(startNode);nodeColor[startNode] = 1;  // 初始化颜色为1while (!nodeQueue.empty()) {int currentNode = nodeQueue.front();nodeQueue.pop();for (int i = head[currentNode]; i != -1; i = nextEdge[i]) {int neighbor = toNode[i];if (nodeColor[neighbor] == -1) {  // 如果邻居未被染色nodeColor[neighbor] = 3 - nodeColor[currentNode];  // 染成不同颜色nodeQueue.push(neighbor);  // 将邻居加入队列} else if (nodeColor[neighbor] == nodeColor[currentNode]) {  // 如果邻居颜色相同return false;  // 不是二分图}}}return true;  // 是二分图
}int main() {cin >> nodeCount >> edgeCount;  // 输入节点数和边数memset(nodeColor, -1, sizeof(nodeColor));  // 初始化颜色数组为-1（未染色）memset(head, -1, sizeof(head));  // 初始化邻接表头指针为-1（无边）// 读取每条边并添加到邻接表for (int i = 0; i < edgeCount; ++i) {int nodeU, nodeV;scanf("%d %d", &nodeU, &nodeV);addEdge(nodeU, nodeV);  // 添加双向边addEdge(nodeV, nodeU);}bool isBipartite = true;// 对每个未染色的节点进行二分图检测for (int i = 1; i <= nodeCount; ++i) {if (nodeColor[i] == -1) {isBipartite = isBipartiteGraph(i);if (!isBipartite) {break;  // 如果发现不是二分图，则直接退出循环}}}// 输出结果if (isBipartite) {cout << "Yes" << endl;} else {cout << "No" << endl;}return 0;
}

匈牙利算法进行二分图匹配

1. 算法原理

匈牙利算法（Hungarian Algorithm）主要用于在二分图中寻找最大匹配。其核心思想是通过增广路径不断扩展匹配，直到无法找到更多的增广路径为止。下面详细介绍匈牙利算法的逻辑和步骤。

2. 匈牙利算法的详细步骤

初始化

初始化匹配：设初始匹配为空集M。
标记已访问的顶点：用一个布尔数组visited来记录当前搜索过程中哪些顶点已经被访问过。

寻找增广路径

对于每个未匹配的顶点u，尝试找到一条增广路径：

选择未匹配的顶点：从未匹配的顶点集合中选择一个顶点u。
深度优先搜索（DFS）或广度优先搜索（BFS）：
- 对于顶点u，遍历其所有邻接顶点v。
- 如果顶点v未被访问且不在当前匹配中，则将其标记为已访问，并继续递归搜索。
- 如果找到一条增广路径，则更新匹配。
更新匹配：一旦找到增广路径，通过翻转路径上边的状态来更新匹配M。
重复上述过程：对所有未匹配的顶点重复上述过程，直到找不到新的增广路径为止。

如下图所示，红色边表示加入匹配的边，黄色高亮是一条增广路径。把增广路径上的边进行反转，就能往匹配中增加一组边。
在这里插入图片描述

2. 伪代码

function Hungarian(Graph):match = 数组，初始化为 -1result = 0for each u in U:visited = 数组，初始化为 Falseif DFS(u, visited, match):result += 1return resultfunction DFS(u, visited, match):for each v in u 的邻接顶点:if not visited[v]:visited[v] = Trueif match[v] == -1 or DFS(match[v], visited, match):match[v] = ureturn Truereturn False

3.代码实现

ACWing 二分图的最大匹配

#include <iostream>
#include <cstring>using namespace std;const int MAX_NODES = 1e5 + 7; // 节点数上限
int head[MAX_NODES], nextEdge[MAX_NODES], edgeTo[MAX_NODES], edgeIdx = 0, matchCount = 0;
bool visited[MAX_NODES];
int matches[MAX_NODES]; // 记录匹配关系// 添加边的函数
void addEdge(int from, int to) {nextEdge[++edgeIdx] = head[from]; // 将新边添加到链表头部head[from] = edgeIdx; // 更新头指针edgeTo[edgeIdx] = to; // 设置边指向的目标节点
}// 深度优先搜索寻找增广路径
bool findAugmentingPath(int person) {for (int i = head[person]; i != -1; i = nextEdge[i]) { // 遍历所有从当前人出发的边int job = edgeTo[i]; // 当前边指向的工作if (!visited[job]) { // 如果该工作未被访问过visited[job] = true; // 标记为已访问/** 如果该工作尚未被匹配，或者之前与该工作匹配的人能够找到新的匹配，* 则更新匹配关系。*/if (matches[job] == 0 || findAugmentingPath(matches[job])) {matches[job] = person; // 更新匹配关系return true;}}}return false; // 找不到增广路径
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n1, n2, m; // n1: 左集合大小, n2: 右集合大小, m: 边的数量cin >> n1 >> n2 >> m;memset(head, -1, sizeof(head)); // 初始化邻接表头指针为-1memset(matches, 0, sizeof(matches)); // 初始化匹配数组为0，表示初始无匹配// 输入边并构建图for (int i = 0; i < m; ++i) {int x, y;cin >> x >> y;addEdge(x, y + n1); // 注意这里y+n1是为了区分二分图的两边}// 尝试为每个人寻找匹配for (int i = 1; i <= n1; ++i) {memset(visited, 0, sizeof(visited)); // 清空访问标记if (findAugmentingPath(i)) {++matchCount; // 成功找到一个匹配则计数加一}}cout << matchCount << endl; // 输出最大匹配数return 0;
}

总结

染色法：用于判定图是否为二分图，时间复杂度为 $O (V + E)$ 。
匈牙利算法：用于求解二分图的最大匹配，时间复杂度为 $\times E)$ 。

通过本文的介绍，读者可以掌握二分图的基本概念、染色法判定二分图的原理、匈牙利算法进行二分图匹配的原理与实现。希望本文能够帮助读者深入理解二分图及其应用。

如果你对二分图或其他图论算法有更多疑问，欢迎在评论区留言讨论！