积分商城

最新搜索： SSD101 jflash stm32 人形机器人 STC8H8K64S4U VIVO
您现在的位置是：首页 > 技术资料 > 用最大流算法求解二分图最大匹配
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

用最大流算法求解二分图最大匹配

更新时间：2026-10-17 10:59:10 大小：38K 上传用户：江岚查看TA发布的资源 标签：最大流算法二分图最大匹配网络流建模匈牙利算法增广路 下载积分：2分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

用最大流算法求解二分图最大匹配 问题定义 给定一个二分图（顶点分为左右两组，边只连接不同组的顶点），求最大匹配，即选择尽可能多的互不相交的边，使每条边连接左右各一个顶点，且每个顶点至多被一条匹配边连接。 例如左边有工人、右边有任务，每个工人可胜任若干任务，求最多能同时安排多少对工人-任务。 问题分析 二分图最大匹配可以通过构建网络流模型求解。核心思想是"增广路"：从匹配出发，不断寻找可增广的路径（从未匹配左顶点出发、交替经过未匹配边与匹配边、到达未匹配右顶点），增广后匹配数加一。 网络流转化 将最大匹配转化为最大流： 增设源点 与汇点 。 连接所有左顶点，容量为 1。 所有右顶点连接 ，容量为 1。 二分图原边从左顶点指向右顶点，容量为 1（或无穷大）。 求 到 的最大流，其流量即为最大匹配数。 C 代码实现（匈牙利算法，DFS增广） c#include

#include#define MAXN 105int matchRight[MAXN]; // 右顶点匹配的左顶点int visited[MAXN]; // 当前增广访问标记int adj[MAXN][MAXN]; // 邻接：左->右int nLeft, nRight;int dfs(int u) { for (int v = 0; v < nRight; v++) { if (adj[u][v] && !visited[v]) { visited[v] = 1; if (matchRight[v] == -1 || dfs(matchRight[v])) { matchRight[v] = u; return 1; } } } return 0;}int maxMatching() { int count = 0; memset(matchRight, -1, sizeof(matchRight)); for (int u = 0; u < nLeft; u++) { memset(visited, 0, sizeof(visited)); if (dfs(u)) count++; } return count;}int main() { nLeft = 3; nRight = 3; memset(adj, 0, sizeof(adj)); adj[0][0] = 1; adj[0][1] = 1; // 左0 可配 右0、右1 adj[1][1] = 1; // 左1 可配 右1 adj[2][2] = 1; // 左2 可配 右2 printf("最大匹配数 = %d\n", maxMatching()); return 0;} 匈牙利算法的核心 匈牙利算法本质是 DFS 寻找增广路：对每个未匹配左顶点，尝试通过其相邻右顶点寻找增广路，若该右顶点已被匹配，则递归尝试"让那个左顶点另寻匹配"。这种"腾挪"使得匹配数不断增加。 复杂度分析 匈牙利算法：时间复杂度 。 基于网络流的 Dinic 算法：。 应用场景 二分图最大匹配广泛用于： 任务分配与人员调度。 配对问题与组合优化。 二分图相关的组合问题。 二分图最大匹配用匈牙利算法通过 DFS 寻找增广路，在 O(V·E) 时间内求出最大匹配数。

部分文件列表

文件名 大小
用最大流算法求解二分图最大匹配.docx 38K

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号