本文介绍多目标跟踪中二分图匹配的匈牙利算法与KM算法。先解释完美匹配、二分图、最大匹配、交错路径等概念，以男女配对为例，演示匈牙利算法流程：通过匹配与寻找增广路径交替操作实现最大匹配，并附代码及输入输出说明，展示算法如何解决二分图无权匹配问题。
☞☞☞AI 智能聊天, 问答助手, AI 智能搜索, 免费无限量使用 DeepSeek R1 模型☜☜☜
多目标跟踪之二分图无权匹配——匈牙利算法（这里以找对象为例）
多目标跟踪加权二分图匹配 ——KM
1 基本概念介绍
- 完美匹配：
考虑部集为X={x1 ,x2, ...}和Y={y1, y2, ...}的二部图，一个完美匹配就是定义从X-Y的一个双射，依次为x1, x2, ... xn找到配对的顶点，最后能够得到 n！个完美匹配。
- 二部图（二分图）：
给定两组顶点，但是组内的任意两个顶点间没有边相连，只有两个集合之间存在边，即组1内的点可以和组2内的点相连，如下图，这样构建出来的图就叫做二部图（更好理解就是n个男人，n个女人，在不考虑同性恋的情况下，组成配偶）
- 最大匹配： 一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
可以看出来，完美匹配一定是最大匹配，而最大匹配不一定是完美匹配。当然，有些情况下我们做不到完美匹配，只能尽可能实现最多的配对，这个就叫做最大匹配。所以，我们的核心目标就是找到最大匹配了。
- 交错路径：
给定图G的一个匹配M，如果一条路径的边交替出现在M中和不出现在M中，我们称之为一条M-交错路径。而如果一条M-交错路径，它的两个端点都不与M中的边关联，我们称这条路径叫做M-增广路径。
2 算法流程
- 男女关系矩阵如下
| 男1 | 男2 | 男3 | |
|---|---|---|---|
| 女1 | 1 | 1 | 1 |
| 女2 | 1 | 0 | 0 |
| 女3 | 1 | 1 | 0 |
- 关系图如下（图线有点歪，迁就看吧），红线表示有关系（未匹配），蓝线表示已匹配
- 第一步：首先给男1进行匹配，发现第一个与其相连的女1还未匹配，将其配对，连上一条蓝线。
- 第二步：接着匹配男2，发现与其相连的第一个目标女1已匹配，这就需要寻找增广路径了。
男2 - 女1 - 男1 - 女2
男2 （未匹配） 女1 （已匹配） 男1 （未匹配） 女2
这有个需要注意的点，就是未匹配和已匹配要交替查找
取反： 男2 （已匹配） 女1 （未匹配） 男1 （已匹配） 女2 如下图
- 第三步：接着匹配男3，发现与其相连的第一个目标女1已匹配，这就又需要寻找增广路径了。
男3 - 女1 - 男2 - 女3
男3 （未匹配） 女1 （已匹配） 男2 （未匹配） 女3
取反：男3 （已匹配） 女1 （未匹配） 男2 （已匹配） 女3
- 去掉红线最终结果（熟悉数据结构的同学现在发现了，查找方法采用了深度优先）
3 代码实现
In [3]
class graph:
def __init__(self,gi,bo): # 输入二部图两个顶点集合的数目，每个集合的顶点均用1, ... , n表示
self.numg=gi # 女孩数量
self.numb=bo # 男孩数量
self.boy={i:[]for i in range(1,bo+1)} # 男孩的可连接对象，建图
self.viag=[0 for i in range(gi+1)] # 记录当前匹配女孩的对象
self.use=[0 for i in range(gi+1)] # 检查女孩是否被搜索过
def add(self,u,v):
self.boy[v].append(u) def find(self,j): # 寻找 j 男孩起始的增广路
if j==0: return 1
for i in self.boy[j]: if self.use[i]==0: # 女孩没有被搜索过
self.use[i]=1
if self.find(self.viag[i]): # 检查 j 匹配女孩后，女孩原男友是否有其它的女友，有则表示存在增广路
self.viag[i]=j return 1
return 0
def Hungarian(self):
sum=0
for i in range(1,self.numb+1): # 检查每个男孩是否能找到女有
self.use = [0 for i in range(self.numg + 1)] # 初始化为0
if self.find(i): sum+=1
return sum,self.viag[1:]if __name__=="__main__":
n,girlnum,boynum = map(int, input().split())
dic = graph(girlnum,boynum) for i in range(n):
a, b = map(int, input().split())
dic.add(a,b) print(dic.Hungarian())# 输入：# 6 3 3 # 1 1# 1 2# 1 3# 2 1# 2 3# 3 1# 输出：# (3, [2, 3, 1])# 输入解释：# 总关系数 男数 女数 （中间空格间隔，每行一回车）# 男1 女1 有关系。。。。# 输出解释# 最大匹配 [2,3,1]表示右集合（女）的序号，分别对应左集合（男）1,2,3(3, [2, 3, 1])
