外观
一文搞懂任务分配中的匈牙利算法与增广路径
问题背景：任务分配为什么是二分图匹配
在排班、派单、资源调度等系统中，经常遇到一类问题：左侧是员工或计算节点，右侧是任务，边表示“某人可以做某项任务”。每项任务最好只分配给一个人，每个人同一时刻也只承担一项任务。目标是在这些限制下让尽可能多的任务被分配。
这正是经典的二分图最大匹配问题。二分图的顶点可以划分为两个互不相交的集合，边只存在于两个集合之间。若选出的边中任意两条都没有公共顶点，就构成一个匹配；边数最多的匹配称为最大匹配。
很多人第一次接触匈牙利算法时，只记住了“尝试匹配、被占就问别人能不能换”的口诀，却没有真正理解增广路径。实际上，匈牙利算法的核心并不是贪心，而是不断寻找增广路径，用一次路径翻转让匹配数严格增加。
方案对比：暴力、贪心与匈牙利算法
最直接的暴力做法是枚举左侧点与右侧任务之间的所有边组合，再判断是否构成匹配。若左侧有 n 个点、边数为 m，组合数可能呈指数增长，只适合极小数据。
普通贪心法按员工顺序选择一个当前空闲任务，速度快，但结果可能不是最优。例如员工 A 能做任务 1、2，员工 B 只能做任务 1。若 A 先选走任务 1，B 就无法分配；而最优方案是 A 做任务 2，B 做任务 1。
匈牙利算法通过 DFS 或 BST 寻找增广路径，能够修正之前看似合理但影响后续匹配的选择。常见 DFS 实现的时间复杂度为 O(VE)，其中 V 是顶点数、E 是边数；使用 BFS 版本的 Hopcroft-Karp 算法可优化到 O(E√V)，但在面试和多数业务规则校验中，DFS 版匈牙利算法更短、更容易验证。
增广路径推导：为什么“腾位置”一定有效
设当前已经选出的匹配边集合为 M。一条路径如果从未匹配的左侧顶点出发，交替经过“不属于 M 的边”和“属于 M 的边”，最后到达一个未匹配的右侧顶点，那么它就是增广路径。
这条路径有三个关键性质：
- 起点和终点都未匹配，所以路径上的非匹配边比匹配边多一条；
- 路径边按“非匹配、匹配、非匹配”交替出现；
- 把路径上的匹配边从 M 中删除，同时把非匹配边加入 M，所有顶点仍然不会重复匹配。
翻转之后，原来的匹配边数量为 k，非匹配边数量为 k+1，新的匹配数就从 k 变成 k+1。因此，只要还存在增广路径，当前匹配就不可能是最大匹配；反过来，如果不存在增广路径，就无法再通过局部调整增加匹配数，此时得到最大匹配。这就是匈牙利算法反复搜索增广路径的理论依据。
所谓“让已占用任务的员工换一个任务”，本质上是在递归寻找这条交替路径，而不是简单地把别人的任务抢过来。
实操步骤：用 DFS 实现匈牙利算法
下面以员工到任务的有向邻接表建模。match_right[v] 表示右侧任务 v 当前分配给哪个员工；visited 用于记录本轮搜索中已经尝试协调过的任务，避免两个员工互相等待形成死循环。
python
# 二分图最大匹配：员工 -> 可执行任务
# 左侧员工编号：0 ~ n-1
# 右侧任务编号：0 ~ m-1
class BipartiteMatcher:
def __init__(self, n_workers, n_tasks):
self.n_workers = n_workers
self.n_tasks = n_tasks
self.graph = [[] for _ in range(n_workers)]
def add_edge(self, worker, task):
# 实际系统中可在此处做权限、技能、时间窗等过滤
self.graph[worker].append(task)
def maximum_matching(self):
# match_right[task] = 当前占用该任务的员工
match_right = [-1] * self.n_tasks
result = []
def dfs(worker, visited):
for task in self.graph[worker]:
# 本轮增广搜索中，每个任务只协调一次
if visited[task]:
continue
visited[task] = True
# 任务空闲，或占用任务的员工能改派到其他任务
owner = match_right[task]
if owner == -1 or dfs(owner, visited):
match_right[task] = worker
return True
return False
for worker in range(self.n_workers):
# 注意：visited 必须每个左部点重新初始化
visited = [False] * self.n_tasks
if dfs(worker, visited):
result.append(worker)
assignments = [
(worker, task)
for task, worker in enumerate(match_right)
if worker != -1
]
return len(assignments), assignments
# 可直接运行的示例
# A: 任务1、任务2；B: 任务1；C: 任务2、任务3
matcher = BipartiteMatcher(n_workers=3, n_tasks=3)
matcher.add_edge(0, 0)
matcher.add_edge(0, 1)
matcher.add_edge(1, 0)
matcher.add_edge(2, 1)
matcher.add_edge(2, 2)
count, assignments = matcher.maximum_matching()
print("最大匹配数：", count)
print("分配结果（员工，任务）：", assignments)执行流程可以概括为：依次处理每个员工；若能直接连接空闲任务就匹配；若目标任务已被占用，则递归尝试让原员工改派；递归成功后沿调用链更新归属；递归失败则说明该员工本轮无法增加匹配。
复杂度分析
设左部点数为 U，右部点数为 V，边数为 E。每个左部点最多触发一次 DFS，一次 DFS 最坏会扫描到大部分边，因此时间复杂度通常写为 O(UE)，在稠密图中也可粗略表示为 O(UV²)。match_right 与 visited 都占用 O(V) 空间，邻接表占用 O(U+V+E)，总空间复杂度为 O(U+V+E)。
如果边数很大、单次只要求最大基数匹配，可以升级为 Hopcroft-Karp：它每轮同时寻找多条最短增广路，把多轮单路增广合并，复杂度可降到 O(E√V)。
从最大匹配到任务分配业务约束
基础匈牙利算法只关心“能不能做”，不关心“谁更适合做”。业务中还可能出现员工负载上限、任务耗时、优先级、技能评分等条件。此时可以根据目标选择不同建模方式。
若每个人最多执行 k 个任务，可以把一个员工拆成 k 个员工节点，每个副本连相同任务边，再求最大匹配。若边带有成本，例如完成时间或费用，并且要求在完美匹配下总成本最小，则应使用带权二分图匹配，即最小权匹配或 KM 算法，而不是继续使用普通匈牙利算法。
需要特别注意：最大匹配只保证匹配边数最大，不保证所有任务都能被分配。若返回数量小于任务数，说明当前技能关系图本身不存在覆盖全部任务的方案，应进一步报告无人可做的任务或冲突位置。
避坑总结：实践中最容易出错的 4 个点
1. 忘记每轮重置 visited，导致递归误判
常见错误是把 visited 定义在 maximum_matching 外层，多个员工共用一份访问标记。现象是前一个员工搜索过的任务，后一个员工即使可以合法增广也被跳过，结果得到偏小的匹配数。修正方法是每次处理新的左部点时重新创建 visited = [False] * n_tasks。它限制的是“本轮协调过程”，不是整个算法生命周期。
2. 在递归 DFS 中提前修改匹配关系
有人会在发现任务被占用时立刻执行 match_right[task] = worker，再去询问原员工能否换任务。一旦后续递归失败，就会出现两个员工同时占用同一任务、原员工归属丢失的问题。正确做法是等 dfs(owner, visited) 返回成功后再更新；若失败，当前匹配状态应保持不变。
3. 邻接表存在重复边，造成性能浪费或结果误读
从数据库或规则引擎生成边时，可能因多个技能标签重复而插入相同 (worker, task)。DFS 通常仍能算出正确匹配数，但会重复扫描边，严重时拖慢接口。修正方法是在建图阶段用集合去重，或写入邻接表前判断任务是否已存在。若还需要展示“命中了哪些规则”，应把规则列表放在额外元数据中，而不是复制图边。
4. 把带成本的最优分配错误地交给最大匹配
普通匈牙利算法看到边就认为权重相同，因此无法表达“员工 A 做任务 1 需要 10 分钟，员工 B 需要 2 小时”这种差异。典型错误现象是匹配数正确，但业务方反馈总耗时或总成本不是最优。若目标是最大可分配数量，用最大匹配；若要求完美匹配下总成本最小，应使用最小权二分图匹配；若容量大于 1，则先拆点或改用网络流模型。
结语
匈牙利算法的价值在于用增广路径把一次性贪心变成可回滚、可修正的匹配过程。理解“非匹配边与匹配边交替、翻转后匹配数加一”之后，递归中的“腾位置”就不再是玄学，而是一条清晰的图论证明链。掌握这一模板后，再面对任务派单、权限配对、资源绑定等问题，就能快速判断问题是否属于二分图匹配，并进一步选择普通匈牙利、拆点建模或带权匹配方案。
免责声明
本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。