本文共 3802 字，大约阅读时间需要 12 分钟。
二分图是一种图论中的重要概念，其特点是图中可以被划分为两个互不相交的点集 X 和 Y。也就是说，图中任意两个点都属于同一个集合时，它们之间不会有边相连。这种结构性质使得二分图在许多实际问题中具有重要意义。
在二分图中，匹配是指图中的一组边，每条边的两个端点在这些边中是唯一的。换句话说，匹配中的每一条边都不会与其他边共享同一个端点。最大匹配则是指在所有可能的匹配中，包含边数最多的匹配。完美匹配则是更进一步的概念，它要求所有的点都能被匹配到，即每个点都位于匹配边的一端。
此外，二分图还有其他重要概念，如最小覆盖和路径覆盖。最小覆盖是指用最少的点（可以是 X 集合或 Y 集合中的任意一个），使得图中每一条边都至少有一个端点属于这些点。路径覆盖则是用尽可能少的路径来覆盖所有的顶点，路径之间不能重复使用顶点。
在二分图中，最小路径覆盖问题可以通过以下公式来解决：路径覆盖数等于顶点数减去最大匹配的大小。具体来说，路径数 S = N - 边数最大的匹配大小。最大独立集问题则可以通过类似的公式来解决：独立集的最大大小等于顶点总数减去最大匹配的大小。
这些性质在图论中具有重要的应用价值，例如在网络流量控制、任务分配等领域，二分图的匹配算法能够有效地解决实际问题。
匈牙利算法是解决二分图最大匹配问题的经典算法。其核心思想是通过深度优先搜索（DFS）来寻找增广路径，这些路径表明存在可以容纳更多匹配边的机会。具体步骤如下：
匈牙利算法通过这种方式不断寻找和调整匹配，最终找到一个最大的匹配。
以下是一个简单的C++代码示例，展示了匈牙利算法的实现：
#include#include #include #include #include using namespace std;int main() { int n, m; int lt[maxn][maxn]; // 邻接矩阵 int link[maxn]; bool used[maxn]; int ans = 0; // 初始化邻接矩阵 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", <[i][j]); } } // 求最大匹配 for (int i = 1; i <= n; ++i) { memset(used, 0, sizeof(used)); if (dfs(i)) { ans++; } } printf("最大匹配数为 %d\n", ans); return 0;}bool dfs(int u) { for (int i = 1; i <= n; ++i) { if (lt[u][i] && !used[i]) { used[i] = true; if (link[i] == -1 || dfs(link[i])) { link[i] = u; return true; } } } return false;}
KM算法是解决带权二分图的最大匹配问题的高效算法。其核心思想是结合贪心算法和匈牙利算法，通过不断调整匹配关系以最大化权值总和。
KM算法的步骤如下：
KM算法通过这种方式能够在二分图中找到权值最大的匹配，适用于带权二分图的最大匹配问题。
以下是一个简单的C++代码示例，展示了KM算法的实现：
#include#include #include #include #include #include using namespace std;int main() { int n, m; int w[1000][1000]; // 权值矩阵 int line[1000], usex[1000], usey[1000]; int cx[1000], cy[1000]; int ans = 0; // 初始化权值矩阵 for (int i = 1; i <= n; ++i) { int d = 0; for (int j = 1; j <= m; ++j) { scanf("%d", &w[i][j]); if (w[i][j] > d) { d = w[i][j]; } } cx[i] = d; } // 求最大权值匹配 while (~scanf("%d%d", &n, &m)) { memset(cy, 0, sizeof(cy)); memset(w, 0, sizeof(w)); memset(cx, 0, sizeof(cx)); for (int i = 1; i <= n; ++i) { int d = 0; for (int j = 1; j <= m; ++j) { scanf("%d", &w[i][j]); if (w[i][j] > d) { d = w[i][j]; } } cx[i] = d; } memset(line, 0, sizeof(line)); ans = km(n, m, w, cx, cy, line); printf("%d\n", ans); } return 0;}// KM算法主函数int km(int n, int m, int w[][1000], int cx[][1000], int cy[][1000], int line[][1000]) { int ans = 0; for (int i = 1; i <= n; ++i) { while (true) { int d = INT_MAX; vector adj; for (int j = 1; j <= m; ++j) { if (!usex[j]) { if (!usey[j]) { d = min(d, cx[j] + cy[i] - w[i][j]); } } } if (d == INT_MAX) { return -1; } for (int j = 1; j <= n; ++j) { if (usex[j]) { cx[j] -= d; } } for (int j = 1; j <= m; ++j) { if (usey[j]) { cy[j] += d; } } for (int j = 1; j <= m; ++j) { if (!usey[j]) { usey[j] = 1; if (line[j] == 0 || km(line[j])) { line[j] = i; return 1; } } } for (int j = 1; j <= n; ++j) { if (usex[j]) { usex[j] = 1; adj.push_back(j); } } queue q; for (int j : adj) { q.push(j); } while (!q.empty()) { int u = q.front(); q.pop(); for (int k = 1; k <= m; ++k) { if (!usey[k]) { if (cx[u] + cy[k] == w[u][k]) { usey[k] = 1; if (line[k] == 0 || km(line[k])) { line[k] = u; return 1; } } } } } } } for (int i = 1; i <= m; ++i) { ans += w[line[i]][i]; } return ans;}
二分图及其匹配算法是图论中的重要研究课题。通过匈牙利算法和KM算法，我们能够高效地解决二分图的最大匹配问题。这类算法在网络流、任务分配等领域具有广泛的应用价值。理解和实现这些算法，不仅有助于解决实际问题，也是提升算法设计能力的重要基础。
转载地址：http://uvki.baihongyu.com/