文章目录

图论中的基本概念匈牙利算法中的基本概念匈牙利匹配算法匈牙利匹配算法举例匈牙利匹配算法Python代码实现

图论中的基本概念

二分图: 一个图中的所有顶点可划分为两个不相交的集合 U 和 V ，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。 匹配: 一个匹配就是一个边的集合，这个边集合中的任意两条边没有公共的顶点。 最大匹配: 一个图的所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。 最大匹配数: 最大匹配的匹配边的数目。 完美匹配: 如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。 最小顶点覆盖数: 选取最少的点，使二分图中任意一条边至少有一个端点被选择。最小覆盖要求用最少的点（U集合或V集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数 最大独立数: 选取最多的点，使任意所选两点均不相连。 最小路径覆盖数: 对于一个 DAG（有向无环图），选取最少条数的路径，使得每个顶点属于且仅属于一条路径，路径长可以为 0（即单个点）。也就是说用尽量少的不相交简单路径覆盖DAG的所有结点。 一些性质: 定理1：最大匹配数=最小点覆盖数（Konig 定理） 定理2：最大匹配数=最大独立数 定理3：最小路径覆盖数=顶点数-最大匹配数

匈牙利算法中的基本概念

交替路: 从一个未匹配的点出发，依次经过非匹配边、匹配边、非匹配边······这样形成的路径叫交替路。 增广路: 从一个未匹配的点出发，走交替路，如果路过一个未匹配的点（第一个点除外），这条交替路叫增广路。 增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。 我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时，达到最大匹配（这是增广路定理）。匈牙利算法正是这么做的，这也是算法的核心。

匈牙利匹配算法

论文:The Hungarian Method for the Assignment Problem 论文地址:https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf 。 重要定理: 如果从一个点A出发，没有找到增广路径，那么无论再从别的点出发找到多少增广路径来改变现在的匹配，从点A出发都永远找不到增广路径。 匈牙利算法的核心思想: 初始时最大匹配为控，然后不断寻找增广路，并扩展增广路。不断重复这一过程直到找不到增广路为止。 如果二分图左半边U集合中共有n个点，那么最多找n条增广路径。如果图中共有m条边，那么每找一条增广路径（DFS或BFS）时最多把所有边遍历一遍，所花时间也就是m。所以总时间大概就是O（nm）。 使用DFS查找的匈牙利匹配算法流程: 从左边U集合找出第一个未匹配点（假设为点1）进行BFS边搜索，寻找一条未匹配边。如果找到一条未匹配边（假设为边1），这个边的另一头是右边V集合中的一个未匹配点（假设为点A），说明寻找成功。更新路径信息，匹配边数+1； 再找到左边U集合的第二个未匹配点（假设为点2），进行BFS边搜索。假如搜索到一条边（假设为边2），该边连接的另一个点V集合中前一轮已经匹配的点（点A），那么我们将边2作为点2和点A的未匹配边，然后对放弃的未匹配边（边1）的另一个点（点1）重新进行BFS边搜索（这次搜索跳过已经选择过的边1），寻找另一条未匹配边。假设我们找到了新的一条为匹配边（边3），该边连接点1和点C。 对于后面的每一轮，我们都从左边U集合中找出一个未匹配点x，然后进行BFS边搜索，如果搜到一条边，其另一点是V集合中前几轮中已经匹配的点y’，那么我们找到y’以前的未匹配边t，找到该边另一头属于左边U集合的点x’，对x’进行BFS边搜索（跳过前面已经选择的边），继续寻找未匹配边。如果x’BFS搜索到下一条边的另一点也是V集合中前几轮中已经匹配的点y’’，那么继续迭代执行上述过程。直到最后迭代找到的点的所有边都搜索过，且找不到为匹配边为止，此时我们就认为本轮最初选择的未匹配点x和点y’无法配对，我们不再从这个点x开始搜索。

匈牙利匹配算法举例

原始二分图中，集合U有点1、2、3、4，集合V中有点5、6、7、8，边有：1-5，1-6，2-5，3-6，3-8，4-7。

1---5 \ / / \ 2 6 / / 3 7 \ / / \ 4 8

第一轮: 选取集合U中未匹配点1，进行BFS边搜索，找到第一条边1-5，5是集合V中未匹配点，这样我们找到了一条边，将集合U的未匹配点1和集合V的未匹配点5配对，我们用link[5] = 1来表示。 第二轮: 接着选取集合U中未匹配的点2，进行BFS边搜索，找到第一条边2-5，但关于5这个点前面已经标记了一个配对边1-5，那么我们再对原来的点1继续进行BFS边搜索，发现另一条边1-6，6是集合V中未匹配点，于是将集合U的未匹配点1和集合V的未匹配点6配对，用link[6] = 1表示，此时link[5] = 1不变，但是要注意它此时的含义是点2和点5配对。 第三轮: 接着选取集合U中未匹配的点3，进行BFS边搜索，找到第一条边3-6，由于link[6] = 1，于是向前找到原来与6配对的点1，对点1再做BFS边搜索，发现边1-5，但点5已经和点2配对了。那么再对点2做BFS边搜索，发现2只有边2-5，搜索到头了只能停止。因此点3不能和点6配对。 再找点3的第二条边，找到边3-8，8是集合V中未匹配点，这样我们将集合U的未匹配点3和集合V的未匹配点8配对，我们用link[8] = 1来表示。 第四轮: 接着选取集合U中未匹配点4，进行BFS边搜索，找到第一条边4-7，7是集合V中未匹配点，这样我们将集合U的未匹配点4和集合V的未匹配点7配对，我们用link[7] = 1来表示。

这样我们就找到了这个二分图的最大匹配。最大匹配中包含的边是1-6，2-5，3-8，4-7。

匈牙利匹配算法Python代码实现

from collections import deque class HungarianAlgorithm(object): def __init__(self, graph): """ 这里的队列虽然用list也可以实现,但pop(0)的开销还是很大,因此还是用链式存储结构Deque :param graph: 二分图的矩阵表示形式 """ self.graph = graph self.length = len(graph) # x为输入的U集合中某个未匹配点，从V集合中寻找另一个未匹配点与其配对 def find(self, x): for i in range(self.length): # V集合中的点从第一个点开始遍历,如果两点之间有边且还没访问过V集合中这个点i if self.graph[x][i] == 1 and not self.used[i]: # 记录匹配边,放入交替路,记录V集合中的点i已访问过 self.used[i] = 1 # 如果点i之前已经访问过 # 如果V集合中的点i之前没有匹配过,或V集合中的点i之前匹配过,那么i的配对点为输入的x,x的配对点位i if self.match[i] == -1 or self.find(self.match[i]) == 1: # 那边令V集合的这个点匹配对象更新为x, self.match[i] = x self.match[x] = i print(x + 1, '->', i + 1) return 1 return 0 def hungarian1(self): """ 递归形式的匈牙利匹配算法 :return: """ # 记录V集合中点的匹配情况的矩阵,一开始全初始化为-1,表示均未匹配 self.match = [-1] * self.length # 记录是否访问过某个点(列表的某个元素,即矩阵的行向量)的矩阵,一开始全为False,表示全未访问过 self.used = [False] * self.length m = 0 # 遍历所有U集合中的点(即列表的每个元素,每一个元素都是一个行向量,记录了这个U集合中的点与V集合中的哪些点有边) for i in range(self.length): # 如果U集合中第i个点还未匹配 if self.match[i] == -1: # 令记录访问过的点记录的矩阵初始化,注意对U集合中每个未匹配点这个矩阵都要重新初始化一次 self.used = [False] * self.length print("开始匹配U集合中第{}个点:".format(i + 1)) m += self.find(i) # 返回的是最大匹配的边个数 return m def hungarian2(self): """ 循环形式的匈牙利匹配算法 :return: """ # 记录V集合中点的匹配情况的矩阵,一开始全初始化为-1,表示均未匹配 match = [-1] * self.length # 记录是否访问过某个点(列表的某个元素,即矩阵的行向量)的矩阵,一开始全为False,表示全未访问过 used = [-1] * self.length # 设置一个队列 q_list = deque() # 记录最大匹配的边个数 ans = 0 # 代表上一个节点 prev = [0] * self.length for i in range(self.length): # 对U集合中第i个点,如果i还没有匹配过,清空队列,i假如队列 if match[i] == -1: q_list.clear() q_list.append(i) # 设i为出发点 prev[i] = -1 # flag=False表示未找到增广路 flag = False # 当队列不为空且还未找到增广路时 while len(q_list) > 0 and not flag: # 队列左边出一个元素(即我们进队列的前面的点,最早进的点先出) u = q_list.popleft() # 查找V集合中的未匹配点 for j in range(self.length): # 如果点U与V集合的点j有边且j的配对点不是i(即还未配对,或配对给其他点) if not flag and self.graph[u][j] == 1 and used[j] != i: # 配对 used[j] = i # 如果u与j已经匹配过 if match[j] != -1: # 把点j也加入队列 q_list.append(match[j]) # 记录点的顺序 prev[match[j]] = u # 如果u与j没有匹配过,现在就开始匹配,且flag=True表示找到增广路 else: flag = True d = u e = j # 将原匹配的边去掉加入原来不在匹配中的边 while (d != -1): t = match[d] match[d] = e match[e] = d d = prev[d] e = t print('match:', match) print('prev:', prev) print('deque', q_list) # 新增匹配边 if match[i] != -1: ans += 1 # 返回的是最大匹配的边个数 return ans # 二分图用矩阵形式存储,即有多少行U集合中集有几个点，有多少列V集合中就有几个点 # 两点之间如果有边则对应位置元素值为1(关于对角线对称) graph_1 = [(0, 0, 0, 0, 1, 0, 1, 0), (0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 0, 0, 1, 1, 0, 0), (0, 0, 0, 0, 0, 0, 1, 1), (1, 1, 1, 0, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0), (1, 0, 0, 1, 0, 0, 0, 0), (0, 0, 0, 1, 0, 0, 0, 0)] def do_hungarian1(graph): h = HungarianAlgorithm(graph) # print(h.graph) # print(h.length) print("最大匹配边数:{}".format(h.hungarian1())) def do_hungarian2(graph): h = HungarianAlgorithm(graph) # print(h.graph) # print(h.length) print("最大匹配边数:{}".format(h.hungarian2())) do_hungarian1(graph_1) do_hungarian2(graph_1)

运行结果如下:

开始匹配U集合中第1个点: 1 -> 5 开始匹配U集合中第2个点: 1 -> 7 2 -> 5 开始匹配U集合中第3个点: 3 -> 6 开始匹配U集合中第4个点: 4 -> 8 最大匹配边数:4 match: [4, -1, -1, -1, 0, -1, -1, -1] prev: [-1, 0, 0, 0, 0, 0, 0, 0] deque deque([]) match: [6, 4, -1, -1, 1, -1, 0, -1] prev: [1, -1, 0, 0, 0, 0, 0, 0] deque deque([]) match: [6, 4, 5, -1, 1, 2, 0, -1] prev: [1, 2, -1, 0, 0, 0, 0, 0] deque deque([1]) match: [6, 4, 5, 7, 1, 2, 0, 3] prev: [3, 2, -1, -1, 0, 0, 0, 0] deque deque([0]) 最大匹配边数:4