多目标跟踪之二分图无权匹配-匈牙利算法

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 行业资讯

多目标跟踪之二分图无权匹配-匈牙利算法

2025-07-31

浏览次数：次

返回列表

本文介绍多目标跟踪中二分图匹配的匈牙利算法与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

Motiff妙多

Motiff妙多是一款AI驱动的界面设计工具，定位为“AI时代设计工具”

334 查看详情 Motiff妙多

这有个需要注意的点，就是未匹配和已匹配要交替查找

取反：男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