二分图及匹配算法

python实现匈⽛利算法求解⼆分图最⼤匹配重点：理解和取反1. 匈⽛利算法求解⽬标：找到⼆分图的最⼤匹配整体思路：每⼀步寻找⼀条增⼴路径，取反2. 关键步骤⼆分图的顶点分为左边点集X和右边点集Y，假定遍历的点集是X。

对于每⼀次迭代的点x_i，1. 搜索增⼴路径：遍历x_i的邻接节点y_j1. 如果y_j未匹配，则找到增⼴路2. 如果y_j已匹配，则寻找y_j的匹配节点的增⼴路径（深搜或者⼴搜）2. 取反：把增⼴路径中的已经匹配边改成未匹配；未匹配的改成匹配3. python代码算法输⼊为字典形式的特殊邻接表。

特殊之处在于字典的键和值的顶点分别属于⼆分图的左右点集合。

深度搜索增⼴路径函数的参数中的visited_set的作⽤是避免重复访问。

# 匈⽛利算法（dfs）class Hungarian:def search_extend_path(self, l_node, adjoin_map, l_match, r_match, visited_set):'''深度搜索增⼴路径'''for r_node in adjoin_map[l_node]: # 邻接节点if r_node not in r_match.keys(): # 情况1：未匹配, 则找到增⼴路径，取反l_match[l_node] = r_noder_match[r_node] = l_nodereturn Trueelse: # 情况2：　已匹配next_l_node = r_match[r_node]if next_l_node not in visited_set:visited_set.add(next_l_node)if self.search_extend_path(next_l_node, adjoin_map, l_match, r_match, visited_set): # 找到增⼴路径，取反l_match[l_node] = r_noder_match[r_node] = l_nodereturn Truereturn Falsedef run(self, adjoin_map):''':param adjoin_map: {x_i: [y_j, y_k]}:return:'''l_match, r_match = {}, {} # 存放匹配for lNode in adjoin_map.keys():self.search_extend_path(lNode, adjoin_map, l_match, r_match, set())return l_match。

最小权匹配算法
最小权匹配算法是一种经典的图论算法，用于在加权二分图中求解最小权匹配。

该算法主要基于匈牙利算法，在其基础上引入了增广路的概念和优化措施，能够更加高效地解决问题。

算法的基本思想是，从左侧顶点开始，依次尝试与其匹配的右侧顶点。

如果右侧顶点已经被匹配，则需要尝试寻找其他未匹配的右侧顶点。

为了避免重复寻找，可以使用一个标记数组记录每个右侧顶点是否已经被访问，从而只需要寻找未被访问的右侧顶点。

在寻找增广路时，算法采用了一种类似于深度优先搜索的方式，通过递归的方式不断寻找未匹配的右侧顶点，直到找到一条已匹配的边为止。

这条已匹配的边将会成为增广路的一部分，然后将会反向匹配所有在增广路上的边，从而完成一次匹配。

为了优化算法效率，可以使用一些技巧，如路径压缩和重贴标记等。

这些技巧可以减少算法的递归次数和标记数组的遍历次数，从而提高算法的运行速度。

最小权匹配算法在实际应用中有着广泛的应用，比如在推荐系统、聚类分析和社交网络等领域。

通过使用该算法，可以快速地找到最佳匹配方案，从而提高系统的推荐准确性和用户体验。

- 1 -。

二分图匹配
匈牙利算法和KM算法简介
二分图的概念
二分图又称作二部图，是图论中的一种特殊 模型。 设G=(V,{R})是一个无向图。如顶点集V可分 割为两个互不相交的子集，并且图中每条边 依附的两个顶点都分属两个不同的子集。则 1 2 3 4 5 称图G为二分图。
1
2
3
4
最大匹配
给定一个二分图G，在G的一个子图M中，M 的边集{E}中的任意两条边都不依附于同一个 顶点，则称M是一个匹配。 选择这样的边数最大的子集称为图的最大匹 最大匹 配问题(maximal matching problem) 配问题 如果一个匹配中，图中的每个顶点都和图中 某条边相关联，则称此匹配为完全匹配 完全匹配，也 完全匹配 称作完备匹配。 完备匹配。 完备匹配
KM算法
穷举的效率－n！，我们需要更加优秀的算法。 定理： 设M是一个带权完全二分图G的一个完备匹配，给 每个顶点一个可行顶标(第i个x顶点的可行标用lx[i] 表示，第j个y顶点的可行标用ly[j]表示)，如果对所 有的边(i,j) in G,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示 边的权)，且对所有的边(i,j) in M,都有lx[i]+ly[j]=w[i,j] 成立，则M是图G的一个最佳匹配。证明很容易。
匈牙利算法
在主程序中调用下面的程序即可得出最大匹 配数。 Bmatch := 0; For I:=1 to n do Bmatch := Bmatch + find(i); Writeln(Bmatch); 一个关于二分图的性质： 最大匹配数＋最大独立集＝X＋Y
最佳匹配
如果边上带权的话，找出权和最大的匹配叫 做求最佳匹配。 实际模型：某公司有职员x1,x2,…,xn,他们去 做工作y1,y2,…,yn,每个职员做各项工作的效 益未必一致，需要制定一个分工方案，使得 人尽其才，让公司获得的总效益最大。 数学模型：G是加权完全二分图，求总权值 最大的完备匹配。

最大权匹配KM算法
KM算法（Kuhn–Munkres算法，也称为匈牙利算法）是由Kuhn于
1955年和Munkres于1957年分别提出的，用于解决二分图最大匹配问题。

该算法的核心思想是基于匈牙利算法的增广路径，通过构建一个增广路径
来不断更新匹配，直到无法找到增广路径为止。

算法流程如下：
2.从G的每个未匹配顶点开始，通过增广路径将其标记为可增广点；
3.当存在增广路径时，将匹配的边进行反向操作，直到不存在增广路径；
4. 利用增广路径的反向操作可以修改lx和ly的值，使其满足特定
约束条件；
5.通过相等子图的扩展来实现增广路径的；
6.重复步骤3-5，直到不存在更多的增广路径；
7.返回找到的最大匹配。

具体实现时，对于增广路径的可以利用DFS或BFS等方法进行，当找
到一个增广路径时，通过反向操作修改匹配情况，并更新lx和ly的值。

同时，算法还可以使用增广路径来调整优化标号，以减少匹配时间。

KM算法是一种高效的解决最大权匹配问题的方法，其时间复杂度为
O(V^3)，其中V为图的顶点数。

算法的核心思想是利用二分图中的相等子
图来查找增广路径，并通过修改顶点的标号来实现最大匹配。

总之，最大权匹配KM算法是一个解决带权无向二分图最大匹配问题
的高效算法，通过不断寻找增广路径并调整顶点的标号来实现最大权匹配。

它的思想简单而有效，可以广泛应用于各种实际问题中。