Ku二分图最大权匹配(KM算法)hn

最大权重匹配算法
最大权重匹配算法也叫做二分图匹配，它是解决二分图中最大匹配问题的一种常见算法。

二分图，顾名思义，就是可以分成两部分的图，即将所有节点分成两部分，使得同一
部分内的节点不连通。

下文中，我们以左侧节点为一部分，右侧节点为一部分。

最大权重匹配算法的目的是，在二分图中找到一种最大匹配方式，并且每条匹配边的
权重之和最大。

在实际问题中，这种算法经常用于任务分配、物流运输、职工配对等方
面。

算法过程：
1. 初始化所有匹配边的权重为0，同时记录每个节点是否被匹配过。

2. 从左侧部分的未匹配节点开始，遍历所有未匹配节点，将其标记为当前选中节
点。

3. 查找与当前选中节点有连通边的所有右侧节点，对于每个右侧节点，都计算出它
和当前选中节点形成的匹配边的权重。

如果该权重比之前已存在的匹配边权重要大，则更
新该匹配边权重，并将当前选中节点和右侧节点确定为一条新的匹配边。

如果需要更新匹
配边，则需要将之前的匹配边删除，统计删除边后，继续查找新的匹配边。

4. 如果当前选中节点不能形成新的匹配边，则回溯到上一个节点，并标记该节点为
已匹配。

5. 重复第2、3、4步操作，直到找出全部最大匹配边。

该算法的时间复杂度为O(n^3)，属于多项式时间内可解决问题的范围，而且是一种较为高效的匹配算法。

但是需要注意的是，该算法必须满足是一个二分图才可以使用。

同时，算法并不能保证是一个最小顶标和、最优匹配的算法，但在大多数情况下，都可以得到较
好的匹配效果。

二分图：二分图是这样的一个图，它的顶点可以分为两个集合X和Y。

所有的边关联的两个顶点中，恰好一个属于集合X，一个属于集合Y。

二分图的匹配：给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

二分图的最大匹配:二分图的所有匹配中包含边数最多的匹配称为图的最大匹配。

完美（完备）匹配：如果所有点都在匹配边上，称这个最大匹配是完美匹配。

最佳匹配：如果边上带权的话，找出权和最大的匹配叫做求最佳匹配。

增广路径：也称增广轨或交错轨。

若P是图G中一条连通两个未匹配顶点的路径，并且属最大匹配边集M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广轨。

定义总是抽象的下面通过图来理解它。

图中的线段（2->3, 3->1, 1->4）便是上面所说的p路径，我们假定边（1,3）是以匹配的边，（2,3）（1,4）是未匹配的边，则边（4,1）边（1,3）和边（3,2）在路径p上交替的出现啦，那么p就是相对于M的一条增广轨，这样我们就可以用边1,4 和边2,3 来替换边1,3 那么以匹配的边集数量就可以加1,。

下面给出关于二分图最大匹配的三个定理1:最大匹配数+ 最大独立集= n + m2:二分图的最小覆盖数= 最大匹配数3:最小路径覆盖= 最大独立集最大独立集是指求一个二分图中最大的一个点集，该点集内的点互不相连。

最小顶点覆盖是指在二分图中，用最少的点，让所有的边至少和一个点有关联。

最小路径覆盖是指一个不含圈的有向图G 中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P 中的某一条路径。

路径可以从任意结点开始和结束，且长度也为任意值，包括0.1求解二分图最大匹配的方法：●匈牙利算法（时间复杂度O(nm)）其思想是是通过不断的寻找增广轨实现最大匹配。

●转化为单位容量简单网络的最大流问题(本文不介绍)在二分图的基础上，加入源点s和汇点t，让s与每个X结点连一条边，每个Y结点和t连一条边，所有弧的容量为1。

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

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

[算法]⼆分图最⼤匹配前⾔具体什么是⼆分图，如何判定，可以参考。

定义简单来说，就是⼆分图中有满⾜任意两条边没有相同的点的边的集合，称为⼀组匹配，⽽边数最多的⼀组匹配称为该⼆分图的最⼤匹配。

在⼀组匹配中，属于这组边的称为匹配边，不属于的称为⾮匹配边，属于这组匹配的点称为匹配点，不属于的称为⾮匹配点。

匈⽛利算法⼜称增⼴路算法。

对于⼀组匹配 \(M\) ，若存在⼀条路径连接两个⾮匹配点，且使得匹配边与⾮匹配边交替出现，则称这条路径为增⼴路。

如上图，已匹配的边为红⾊，未匹配的边为绿⾊，则可以找到⼀组增⼴路 \(8\) ~ \(2\) ~ \(7\) ~ \(4\) 。

不难发现增⼴路具有以下特点：以⾮匹配边开始，在以⾮匹配边结尾，那么长度必为奇数。

路径上第⼀条边因为第⼀个点为奇数，则该路径上的第⼀个点为⾮匹配边，按照匹配边与⾮匹配边交替出现的性质可以得出，该路径的第奇数条边必为⾮匹配边，已经匹配的边必为第偶数条边，则有⾮匹配边的边数⽐匹配边的边数多⼀。

最⼤匹配中不会有增⼴路。

证明：假设最⼤匹配中存在增⼴路，则可以将增⼴路中的所有边的状态取反（即把⾮匹配边转换为匹配边，将匹配边转换为⾮匹配边），得到另⼀组匹配，⽽这组匹配的匹配边肯定会⽐之前的⼀组匹配的边数多⼀，则之前的这组匹配就不是最⼤匹配，与假设⽭盾，证毕。

在⼀张⼆分图中，若最⼤匹配为 \(S\) ，当且仅当 \(S\) 中不存在增⼴路。

其确性基于 \(hall\) 定理，⽐较复杂就不在详讲，主要讲找⼆分图最⼤匹配的⽅法。

⼤体思想就是枚举左部点，找到增⼴路后将这条路上的所有边的状态取反，得到边数更⼤的⼀组匹配。

在匹配过程中，有两种情况会改变当前左部点 \(u\) 的匹配情况。

1. 与之对应的右部点 \(v\) 是⾮匹配点，则可以将其的连边变为匹配边。

2. 与之对应的右部点 \(v\) 是匹配点，但与 \(v\) 已经匹配的点 \(u'\) 可以找到另⼀个未匹配的右部点 \(v'\) ，则 \(u\) ~ \(v\) ~ \(u'\) ~ \(v'\) 为⼀条增⼴路，则将其状态取反。

改进的km 算法流程-回复改进的KM算法流程引言KM算法，即Kuhn-Munkres算法，也被称为匈牙利算法，是一种用于解决二分图最大权匹配问题的经典算法。

它在应用中被广泛使用，例如在任务分配、资源分配、航线规划等领域。

然而，KM算法在处理大规模问题时存在效率低下的问题。

为了提高算法的性能，学者们不断进行改进和优化。

本文将介绍改进后的KM算法的流程，并逐步解释每个步骤的具体操作。

一、问题描述在介绍改进的KM算法之前，首先需要明确问题的描述。

给定一个二分图，其中左侧顶点集合为X，右侧顶点集合为Y，边权重矩阵为C。

目标是找到一个匹配M，使得M中所有边的权重之和最大。

二、改进算法的基本思路改进的KM算法主要通过两个步骤来提高效率：启发式初始化和优化的增广路径寻找。

1. 启发式初始化：将初始标号设置为最小权重值2. 优化的增广路径寻找：通过DFS（深度优先搜索）和BFS（广度优先搜索）寻找增广路径下面将详细介绍这两个步骤。

三、启发式初始化启发式初始化的目的是在算法初始阶段就为每个顶点设置一个初始标号，以便减少后续迭代中的计算量。

具体步骤如下：1. 初始化顶点集合X和Y的标号为0。

2. 对于每个左侧顶点x∈X，找到该顶点对应的最大权重，将该权重作为左侧顶点x的初始标号。

3. 更新右侧顶点y∈Y的标号为与它相连的左侧顶点的初始标号中的最大值。

四、优化的增广路径寻找优化的增广路径寻找是通过DFS和BFS结合的方式来寻找增广路径，其中DFS用于尽可能延伸已有的匹配集，而BFS用于寻找未被匹配的顶点。

1. 初始化路径集合P为空。

2. 对于每个未匹配的左侧顶点x∈X，将x添加到路径集合P中。

3. 对于路径集合P中的每个顶点u，如果u是未匹配的左侧顶点，则将u的相邻未匹配右侧顶点v添加到路径集合P中，并将v的前驱节点设置为u。

4. 如果路径集合P中存在一条从未匹配的左侧顶点x开始，以交替的形式经过已匹配的边和未匹配的边，并最终达到未匹配的右侧顶点y的路径，那么就找到了一条增广路径。

二分图匹配算法及其应用【文献综述】文献综述数学与应用数学二分图匹配算法及其应用图的匹配理论简单的说就是使得图G 中每两个点之间都有联系. 匹配理论是图论中的一个重要内容, 它在运筹学、系统工程中都有着广泛的应用, 近几十年来, 随着组合数学的迅速发展, 匹配理论成为许多重要理论的基础和源泉. 二分图的最大匹配算法是匹配理论研究的热点之一. KM 算法是求最大匹配的经典算法, 它是在匈牙利算法的进一步提高, 它是解决数学中一类存在性问题的基本工具, 广泛应用于社会、经济、科技、自然等各个领域中. 本文主要研究KM 算法的具体原理, 步骤, 以及它一些实际问题中的应用.图的匹配问题起源于1935年霍尔的“婚姻问题”. KM 算法是Kuhn 和Munkras 分别于1955年和1957年独立提出来的, 他们在研究图论中最大权匹配问题时很巧妙运用KM 算法去解决问题.定义1 图G 有三部分所组成(1) 非空集合)(G V , 称为G 的结点集, 其成员称为结点或顶点.(2) 集合)(G E , 称为G 的边集, 其成员称为边.(3) 函数))(),(()(:G V G V G E G →ψ,称为边和顶点的关联映射. 这里))(),((G V G V 称为)(G V 的偶对集, 其成员偶对形如),(v u , u ,v 为结点, 它们未必不同. 当),()(v u e G =ψ时, 称边e 关联端点u ,v . 当),(v u 用作序偶时)()())(),((G V G V G V G V ?=,e 称为有向边, e 以u 为起点, 以v 为终点, 图G 称为有向图; 当),(v u 用作无序偶对时, ),(),(u v v u =, 称e 为无向边(或边), 图G 称为无向图(或图). 定义2 无向图?ψ?=,,E V G 称为二分图, 如果有非空集合X ,Y 使V Y X =Y ,X Y =?I ,且对每一E e ∈, ),()(y x e =ψ, X x ∈,Y y ∈. 此时常用?ψ?,,E V 表示二分图G . 若对X 中任一x 及Y 中的任一y 恰有一边E e ∈, 使),()(y x e =ψ, 则称G 为完全二分图. 当m X =, n Y =时, 完全二分图G 记为n m K ,.定义3 图G 的顶点1v 到顶点l v 的拟路径是指如下顶点与边的序列:l l l v e v v e v e v ,,,,,,,1132211--Λ其中l l v v v v v ,,,,,1321-Λ为G 的顶点, 121,,,-l e e e Λ为G 的边, 且)1,,2,1(-=l i e i Λ以i v 及1+i v 为端点(对有向图G , i e 以i v 为起点, 以1+i v 为终点). 当)1,,2,1(-=l i e i Λ各不相同时, 该拟路径称为路径.定义4 若M 是二分图),(E V G =的一个匹配. 设从图G 中的一个顶点到另一个顶点存在一条路径, 这条路是由属于M 的边和不属于M 的边P 交替出现组成的, 则称这条路为增广路(或称交互树或交错树). 如果增广路的首尾两个顶点不属于M , 则称这条路为可增广路.定义 5 设?ψ?=,,E V G 为二分图, 当给G 赋予映射W V f →:或W E g →:, W 为任意集合、常用实数集及其子集, 此时G 为赋权图, 常用?ψ?f E V ,,,或?ψ?g E V ,,,或?ψ?g f E V ,,,,表示之. )(v f 称为结点v 的权, )(e g 称为e 的权.定义6 设??=Y E X G ,,为二分图, E M ?. 称M 为G 的一个匹配, 如果M 中任何两条边都没有公共端点. G 的所有匹配中边数最多的匹配称为最大匹配, 其边数称为匹配数. 如果X (Y )中任一顶点均为匹配M 中边的端点, 那么称M 为X (Y )—完全匹配. 若M 既是X —完全匹配又是Y —完全匹配, 则称M 为G 的完全匹配.定义7 设二分图??=Y E X G ,,, 其中X =Y =匹配数, E 中每条边),(j i Y X 有权0,≥j i W , 若能找到一个匹配M (M =匹配数), 满足所有匹配的边权和最大(或最小), 则称M 为G 的一个最大(或最小)权匹配.定义8 称图中顶点u 到v 是可达的, 如果v u =, 或者有一条u 到v 的路径. 如果G 的任何两个顶点都是互相可达的, 称无向图G 是连通的. 如果G '是G 的子图,G '是连通的, 并且不存在G 的真子图G '', 使G ''是连通的, 且G ''以G '为真子图, 则图G '称为图G 的连通分支.定理1(霍尔定理) 设图??=Y E X G ,,. G 有X —完全匹配的充分必要条件是: 对每一X S ?, 其中)(S N 为S 的邻域, 即Y S v ii v N S N ∈=)()(, 则有S S N ≥)(.定理2(Tutte 定理) 一个图G 有完全匹配当且仅当对图G 的任意顶点子集S 有图S G -的奇分支数不大于S 中的顶点数, 其中S G -表示从图G 中删去顶点集S 及其关联的边所得的图, 图的奇分支是指奇数个顶点的连通分支.定理3 若由二分图中所有满足j i j i W Y X ,=+的边(,)i j 构成的子图(称做相等子图)有完全匹配, 那么这个完全匹配就是二分图的最大权匹配.Kuhn －Munkras 算法(即KM 算法)流程(1) 初始化可行顶标的值;(2) 用匈牙利算法寻找完备匹配;(3) 若未找到完全匹配则修改可行顶标的值;(4) 重复(2)(3)直到找到相等子图的完全匹配为止.KM 算法是通过给每个顶点一个标号(我们有时称之为顶标)来把求最大权匹配的问题转化为不断地寻找增广路以使二分图的匹配数达到最大的完全匹配的问题. 我们令二分图中X 部的节点的顶标为i X . Y 部的节点的顶标为j Y . X 部与Y 部节点之间的权值为j i W ,. 要求在算法执行过程中的任一时刻，对于任一条边(,)i j , 使得j i j i W Y X ,≥+始终成立. 在初始时, 令i X 为所有与顶点i X 关联的边的权值的最大值, 令0=i Y . 如果当前的相等子图没有完全匹配, 就需要修改顶标以使扩大相等子图, 直到相等子图具有完全匹配为止(这样就可以求出最大权匹配).如果当前相等子图找不到完全匹配, 那么是因为对于某个X 顶点, 我们找不到一条从它出发的增广路. 这时为了获得了一条增广路, 现在我们把增广路中X 的顶点的顶标全都减小某个值d , Y 的顶点的顶标全都增加d , 就可以使得至少有一条新边进入相等子图. 那么我们会发现:(1) 两端都在增广路中的边(,)i j , j i Y X +的值没有变化. 也就是说, 它原来属于相等子图, 现在仍属于相等子图.(2) 两端都不在增广路中的边(,)i j , i X 和j Y 都没有变化. 也就是说, 它原来属于(或不属于)相等子图, 现在仍属于(或不属于)相等子图.(3) X 端不在增广路中, Y 端在增广路中的边(,)i j , 它的j i Y X +的值有所增大. 它原来不属于相等子图, 现在仍不属于相等子图.(4) X 端在增广路中, Y 端不在增广路中的边(,)i j , 它的j i Y X +的值有所减小. 也就说, 它原来不属于相等子图, 现在可能进入了相等子图, 因而使相等子图得到了扩大.现在的问题就是求d 值了. 为了使j i j i W Y X ,≥+始终成立, 且至少有一条边进入相等子图, 则}min{,j i j i W Y X d -+=, 而且i X 在增广路中, j Y 不在增广路中.刘桂真[1]对二分图最大权匹配开讨论, 介绍了二分图最大权匹配并将匹配问题从“婚姻问题”推广到工作分派问题.耿素云[2]通过对二分图的匹配及带权图的应用进行了讨论也将其运用到实际中, 并以此解决了最短路径的问题、关键路径问题以及中国邮递员问题.杨胜超、张瑞军[3]在介绍毕业论文选题系统的系统用例、功能模块、和流程图的基础上, 针对学生选题不均衡这一突出问题, 引出了二分图最大权匹配的经典算法—KM 算法, 该算法能够根据学生的题目预选、自命题、未定题等多种情况, 完成题目与学生的智能匹配, 使最终题目的整体满意度最高, 从而提高学生毕业论文选题质量. 该系统在武汉科技大学管理学院04级毕业论文选题中实施.谢政、程浩光[4]利用赋双权的二分图中求关于第一个权最大的限制下、第二个权最小的完美匹配的网络模型, 给出了这一模型的有效性, 并用此算法解决了企业的优化组合分工中的挖潜问题.彭宇新, Ngo Chong-Wah, 肖建国[5]利用尝试将二分图的最大权匹配用于镜头检索. 把两个镜头的相似度度量建模为一个带权的二分图: 镜头中的每一帧看成二分图的一个结点, 两个镜头之间任意帧的相似值作为边的权值. 在一一对应的前提下, 利用最大权匹配的KM 算法求出该二分图的最大权, 以此作为两个镜头的相似度. 考虑到检索的速度的问题, 提出了两个改进算法.对于二分图最大权匹配的算法有不少, 如: 顶点标记法等. 但KM 算法是求解二分图最大权匹配的经典算法. 本文主要研究用KM 算法解决二分图最大权匹配的步骤过程及二分图最大权匹配算法的应用. 特别是在解决工作分派问题上以及其他实际问题中的应用.。

km算法原理KM算法原理：带权二分图最大权完美匹配KM算法全称为Kuhn-Munkres算法，是一种求解带权二分图最大权完美匹配的算法。

该算法的时间复杂度为O(n^3)，相较于暴力枚举的O(n!)和网络流的O(n^4)，其效率更高。

我们来了解一下什么是带权二分图。

带权二分图是指一个无向图G=(V, E)，其中V可以划分为两个集合X和Y，使得X和Y内部的点没有边相连，而X和Y之间的点有边相连，并且每条边都有一个权值。

我们的目标是找到X到Y的最大权匹配。

KM算法的思路是不断尝试寻找增广路，并将其加入当前匹配中。

增广路是指从未匹配的点开始，经过一系列已匹配的点，最终到达另一个未匹配的点的路径。

如果当前匹配中不存在增广路，那么我们就找到了最大权匹配。

具体实现时，我们需要使用两个数组：lx和ly。

lx[i]表示左边第i个点的最大权值，ly[j]表示右边第j个点的最大权值。

初始时，我们将lx[i]=max{w[i][j]}，其中w[i][j]表示左边第i个点到右边第j个点的边权值，ly[j]=0。

然后我们不断进行匹配，直到没有增广路为止。

匹配的过程中，我们需要使用一个vis数组记录右边第j个点是否被访问过。

如果右边第j个点未被访问，我们就尝试匹配左边第i个点和右边第j个点，如果匹配成功，就更新lx[i]和ly[j]的值。

如果匹配失败，我们就需要尝试将当前匹配中的某个点切换到另一个点上，以获得更大的权值。

这个过程可以通过递归实现。

我们得到的匹配就是带权二分图的最大权完美匹配。

KM算法的时间复杂度为O(n^3)，空间复杂度为O(n^2)。

KM算法是一种高效的求解带权二分图最大权完美匹配的算法。

它的思路简单，实现也不难，但需要注意细节和边界条件。

在实际应用中，KM算法可以用于匹配问题、优化问题等方面。

二分图匹配算法总结 (by phoenixinter, Aug 2006)最近下决心要把二分图匹配部分的算法都搞搞清楚，努力了几天之后基本上搞定了，下面做一个这个专题的总结。

一、二分图最大匹配二分图最大匹配的经典匈牙利算法是由Edmonds在1965年提出的，算法的核心就是根据一个初始匹配不停的找增广路，直到没有增广路为止。

匈牙利算法的本质实际上和基于增广路特性的最大流算法还是相似的，只需要注意两点：（一）每个X节点都最多做一次增广路的起点；（二）如果一个Y节点已经匹配了，那么增广路到这儿的时候唯一的路径是走到Y节点的匹配点（可以回忆最大流算法中的后向边，这个时候后向边是可以增流的）。

找增广路的时候既可以采用dfs也可以采用bfs，两者都可以保证O(nm)的复杂度，因为每找一条增广路的复杂度是O(m)，而最多增广n次，dfs在实际实现中更加简短。

二、Hopcroft-Karp算法SRbGa很早就介绍过这个算法，它可以做到O(sqrt(n)*e)的时间复杂度，并且在实际使用中效果不错而且算法本身并不复杂。

Hopcroft-Karp算法是Hopcroft和Karp在1972年提出的，该算法的主要思想是在每次增广的时候不是找一条增广路而是同时找几条点不相交的最短增广路，形成极大增广路集，随后可以沿着这几条增广路同时进行增广。

可以证明在寻找增广路集的每一个阶段所寻找到的最短增广路都具有相等的长度，并且随着算法的进行最短增广路的长度是越来越长的，更进一步的分析可以证明最多只需要增广ceil(sqrt(n))次就可以得到最大匹配（证明在这里略去）。

因此现在的主要难度就是在O(e)的时间复杂度内找到极大最短增广路集，思路并不复杂，首先从所有X的未盖点进行BFS，BFS之后对每个X节点和Y节点维护距离标号，如果Y节点是未盖点那么就找到了一条最短增广路，BFS完之后就找到了最短增广路集，随后可以直接用DFS对所有允许弧(dist[y]=dist[x]+ 1，可以参见高流推进HLPP的实现)进行类似于匈牙利中寻找增广路的操作，这样就可以做到O(m)的复杂度。

km(kuhn-munkres)算法的具体表达KM算法，即Kuhn-Munkres算法（又称为匈牙利算法），是一种用于求解二分图最大权匹配问题的经典算法。

它由Eugene L. Lawler于1960年首次提出，后来由James Munkres在1957年独立发表，因此常称为Kuhn-Munkres算法。

二分图最大权匹配问题是指给定一个带权二分图，要求在图中选取权重之和最大的边集合，使得任意两条边不属于同一个顶点。

其中，带权二分图是指图的每条边都带有一个非负权重。

KM算法使用了两个关键的概念：交错树和相等子图。

交错树是指一个T=（S，P）的有向树，其中S是原二分图的所有顶点的集合，P是树中的边集合。

相等子图是指原二分图的一个子图，其中T中所有入树边的权重之和等于所有出树边的权重之和。

KM算法具体的步骤如下：1.初始化：将图中所有边的权重初始化为0，构建了一个初始的交错树T=（X，Y）（其中X，Y分别表示两个顶点集合）。

2.判断相等子图：对于T中的每个顶点x，如果存在一条满足lx+ly=W（其中lx是x在T中所有入树边的权重之和，ly是x在T中所有出树边的权重之和，W是x在原图G中的权重），则把x加入到相等子图中。

3.寻找未匹配节点：在相等子图中寻找未匹配节点，并标记为未父节点。

4.寻找增广路：如果存在未匹配节点，则从中选择一个起始节点，寻找一条与之交替出现的边构成的路径，使路径的最后一个边是一条与未匹配节点关联的边。

这样的路径称为增广路。

5.修改标号：对于相等子图中的每个顶点x，从已匹配节点中选择一个与之关联的顶点y，并计算d=min(lx+ly-w)（其中w是x和y之间的边的权重），为了使增广路更优，将T中所有x节点的入树边的权重减去d，将T中所有y节点的出树边的权重加上d。

6.更新交错树：将增广路中的所有边和T中的所有非树边进行调整，得到新的交错树。

7.重复步骤3-6，直到没有未匹配节点为止。

[二分图带权匹配与最佳匹配]什么是二分图的带权匹配？二分图的带权匹配就是求出一个匹配集合，使得集合中边的权值之和最大或最小。

而二分图的最佳匹配则一定为完备匹配，在此基础上，才要求匹配的边权值之和最大或最小。

二分图的带权匹配与最佳匹配不等价，也不互相包含。

我们可以使用KM算法实现求二分图的最佳匹配。

方法我不再赘述，可以参考tianyi的讲解。

KM算法可以实现为O(N^3)。

[KM算法的几种转化]KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。

KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。

KM算法求得的最大权匹配是边权值和最大，如果我想要边权之积最大，又怎样转化？还是不难办到，每条边权取自然对数，然后求最大和权匹配，求得的结果a再算出e^a就是最大积匹配。

至于精度问题则没有更好的办法了。

[求最小(大)权匹配的费用流建模方法]求最小(大)权匹配，可以用最小(大)费用最大流的方法。

和二分图最大匹配的构图方法类似，添加附加源S和附加汇T，从S向二分图X集合中每个顶点连接一条权值为0，容量为1的有向边，从Y集合中每个顶点向T也连接一条权值为0，容量为1的有向边。

然后把原有的边变成容量为1，权值不变的有向边。

求从S到T的最小(大)费用最大流，就能求得最小(大)权匹配。

上述建模求最大权匹配的方法求得的一定是最佳匹配(如果存在完备匹配)，因为S到X集合每条边全部满流。

如下图所示，最小费用最大流为2。

要求最大权匹配(不一定完备匹配)。

如下图，只需再引入一个顶点A，从X集合的每个顶点向A连接一条容量为1，权值为0的边，然后再由A向T连接一条权值为0，容量不小于|X|的边，求最大费用最大流，这时是100。

最小权匹配也类似，不过新加的边权要为一个极大值，大于所有已有边权值。

最大权匹配KM算法KM 算法（Kuhn–Munkres 算法）又被称为匈牙利算法或者二分图最佳匹配算法，是用来解决二分图最大权匹配问题的一种有效算法。

它的时间复杂度为 O(n^3)，其中 n 是二分图中的顶点数。

在二分图最大权匹配问题中，给定一个二分图，找到一种边的匹配方式，使得所有边的权重之和达到最大。

其中，二分图是一种图，其顶点可以分为两个不相交的集合U和V，并且图中的每条边都连接U和V中的两个顶点之一KM 算法的主要思想是通过设置两个顶标数组 lx 和 ly 来记录每个顶点的可行匹配权值。

算法的基本步骤如下：1. 初始化顶标数组 lx 和 ly 为 0。

2. 对于每个顶点 u 属于集合 U，找出 u 在集合 V 中的邻接顶点 v，计算顶点 u 和 v 之间的权值与当前顶标数组的差值 delta，如果 delta 大于顶点 v 的顶标，则更新顶标 lx[u] 为 delta。

3.从集合U中选择一个顶点u，对于该顶点u在集合V中的每个邻接顶点v，如果u和v当前没有匹配，则尝试将u和v进行匹配，并将顶点u标记为已匹配。

4. 如果存在未匹配的顶点，则尝试改变标号以寻找更大的匹配权重。

具体操作是分别减小顶标 lx[u] 和增加顶标 ly[v]，保持所有匹配的边不变。

5.重复步骤2-4，直到无法找到更大权重的匹配。

KM 算法的关键在于通过改变顶标数组 lx 和 ly，以及不断改变已匹配的顶点来寻找更大的权重匹配。

当顶标数组不再改变时，即找到了最大权匹配。

需要注意的是，KM算法只能解决二分图的最大权匹配，如果给定的图不是二分图，需要先进行二分图的判定。

此外，KM算法也可以用来解决最小权匹配问题，只需要将边的权重取相反数即可。

总结来说，KM算法通过设置顶标数组和不断改变匹配的顶点来寻找二分图的最大权匹配。

它是一种时间复杂度较低、效率较高的算法，有着广泛的应用场景，例如任务分配、资源分配等问题。

二分图最大权匹配 KM算法KM算法的正确性基于以下定理：若由二分图中所有满足A[i]+B[i]=w[i][j]的边C（i，j）构成的子图（即相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配基本概念1.完备匹配设G=V1,V2,E为二分图，|V1|=|V2|,M为G中的一个最大匹配，且|M|=V1,则称M为V1到V2的完备匹配。

通俗的理解，就是把V1中所有的点都匹配完2.可行顶标对于左边的点设为LX[maxn]数组，右边的点设为LY[maxn]数组，w[i][j]表示 v[i] 到 v[j] 的权值3.相等子图相等子图为完备匹配中所有的匹配，即全部V1中的点和与V1中的点匹配的V2中的点，但是边只包含 LX[i]+LY[j]=W[i][j]的边4.最优完备匹配最优完备匹配就是在完备匹配的条件下求解权值最大或者最小，若由二分图中所有满足A[i]+B[i]=W[i][j]的边C（i，j）构成的相等子图有完备匹配，那么这个完备匹配就是二分图的最大权匹配因为对于二分图的任意一个匹配，如果它包含相等子图，那么它的边权和等于所有顶点的顶标和；如果它有边不包含于相等子图，那么它的边权和小于所有顶点的顶标和，所以相等子图的完备匹配，一定是二分图的最大权匹配。

5.交错树对V1中的一个顶点进行匹配的时候，所标记过的V1，V2中的点以及连线，形成一个树状的图KM算法原理1.基本原理该算法是通过给每个顶点一个标号(叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题。

设顶点V1的顶标lx[i]，V2顶点的顶标为LY[j],顶点V1的i与V2的j之间的边权为V(i,j)。

在算法执行的过程中，对于任一条边C(i,j)，LX[i]+LY[i]=V[i,j]始终成立2.基本流程（1）初始化时为了使 LX[i] + LY[j] = V [i,j]恒成立，将V1的点的标号记为与其相连的最大边权值，V2的点标号记为0 （2）用匈牙利算法在相等子图寻找完备匹配（3）若未找到完备匹配，则修改可行顶标的值，扩充相等子图（4）重复（2）（3）直到找到相等子图的完备匹配为止3.这里值得注意的是找完备匹配不难理解，主要是进行可行顶标的修改扩充相等子图朴素的实现方法：时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。

⼆分图匹配之最佳匹配——KM算法今天也⼤致学了下KM算法，⽤于求⼆分图匹配的最佳匹配。

何为最佳？我们能⽤匈⽛利算法对⼆分图进⾏最⼤匹配，但匹配的⽅式不唯⼀，如果我们假设每条边有权值，那么⼀定会存在⼀个最⼤权值的匹配情况，但对于KM算法的话这个情况有点特殊，这个匹配情况是要在完全匹配（就是各个点都能⼀⼀对应另⼀个点）情况下的前提。

⾃然，KM算法跟匈⽛利算法有相似之处。

其算法步骤如下：1.⽤邻接矩阵（或其他⽅法也⾏啦）来储存图，注意：如果只是想求最⼤权值匹配⽽不要求是完全匹配的话，请把各个不相连的边的权值设置为0。

2.运⽤贪⼼算法初始化标杆。

3.运⽤匈⽛利算法找到完备匹配。

4.如果找不到，则通过修改标杆，增加⼀些边。

5.重复3，4的步骤，直到完全匹配时可结束。

⼀⾔不合地冒出了个标杆？？标杆是什么？？？在解释这个问题之前，我们先来假设⼀个很简单的情况，⽤我们⼈类伟⼤的智能思维去思考思考。

如上的⼀个⼆分图，我们要求它的最⼤权值匹配（最佳匹配）我们可以思索思索⼆分图最佳匹配还是⼆分图匹配，所以跟和匈⽛利算法思路差不多⼆分图是特殊的⽹络流，最佳匹配相当于求最⼤（⼩）费⽤最⼤流，所以FF⽅法也能实现所以我们可以把这匈⽛利算法和FF⽅法结合起来FF⽅法⾥⾯，我们每次是找最长（短）路进⾏通流所以⼆分图匹配⾥⾯我们也找最⼤边进⾏连边!但是遇到某个点被匹配了两次怎么办？那就⽤匈⽛利算法进⾏更改匹配！这就是KM算法的思路了：尽量找最⼤的边进⾏连边，如果不能则换⼀条较⼤的。

所以，根据KM算法的思路，我们⼀开始要对边权值最⼤的进⾏连线，那问题就来了，我们如何让计算机知道该点对应的权值最⼤的边是哪⼀条？或许我们可以通过某种⽅式记录边的另⼀端点，但是呢，后⾯还要涉及改边，⼜要记录边权值总和，⽽这个记录端点⽅法似乎有点⿇烦，于是KM采⽤了⼀种⼗分巧妙的办法（也是KM算法思想的精髓）：添加标杆（顶标）是怎样⼦呢？我们对左边每个点Xi和右边每个点Yi添加标杆Cx和Cy。

改进的KM算法流程KM算法（Kuhn-Munkres算法）是一种用于解决二分图最大匹配问题的经典算法，但是在实际应用中，由于数据量大、维度高等原因，传统的KM算法效率较低。

本文将针对KM算法进行改进，详细说明改进后的算法流程。

1. 问题定义- 最大匹配问题是指在一个二分图中，找到一个最大的匹配，使得图中的边数最大化，即找到尽可能多的边，使得每个顶点都与某条边相关联。

2. 原始KM算法流程回顾- 在原始KM算法中，首先需要初始化顶标和匹配数组，然后通过不断调整顶标和匹配数组来寻找增广路径，直到无法找到增广路径为止。

3. 改进思路- 我们可以通过优化顶标调整的策略，以及采用更高效的数据结构来加速算法的执行。

同时，可以引入并行计算来提高算法的并发性能。

4. 改进后的算法流程- 初始化顶标和匹配数组：与原始KM算法相同。

- 通过优化的顶标调整策略来寻找增广路径：可以采用更高效的寻找增广路径的方法，如Dijkstra算法等。

- 并行计算：利用多线程或分布式计算来加速算法的执行，提高算法的并发性能。

- 更新匹配数组：根据找到的增广路径来更新匹配数组。

- 判断终止条件：如果无法找到增广路径，算法终止，得到最大匹配。

5. 算法分析- 通过优化顶标调整策略和引入并行计算，改进后的KM算法在处理大规模数据时具有更高的效率和并发性能。

- 改进后的算法能够更快地找到最大匹配，并且在实际应用中具有更好的适用性和稳定性。

6. 实验与评估- 我们可以通过对比原始KM算法和改进后的KM算法在不同规模数据上的执行时间和匹配结果来评估改进后算法的效果。

- 通过实验结果的对比分析，可以验证改进后的KM算法在效率和性能上的提升。

7. 结论- 通过对KM算法的改进，我们能够更好地解决二分图最大匹配问题，提高算法的执行效率和并发性能，使其更适用于处理大规模数据和高维度问题。

通过以上流程，我们详细说明了改进的KM算法流程，包括问题定义、原始算法回顾、改进思路、改进后的算法流程、算法分析、实验与评估以及结论。

⼆分图匹配问题最⼤匹配以及相关结论多重匹配最⼤带权匹配带花树算法⼆分图匹配问题：做法：①匈⽛利算法，时间复杂度O(N*V)②Hopcroft-Karp，时间复杂度O(√N*V)相关结论：①最⼩顶点覆盖(könig定理)　⼆分图的最⼩顶点覆盖=最⼤匹配数②最⼩路径覆盖（不要求⼆分图）：在图中找⼀些路径，使之覆盖了图中的所有顶点，且任何⼀个顶点有且只有⼀条路径与之关　最⼩路径覆盖 = 顶点数 - 最⼤匹配配对于有向⽆环图，⾸先拆点，建成⼆分图再进⾏求解·最⼩不相交路径覆盖　建图⽅式:把⼀个的点V拆点成Vx和Vy，如果A连向B，那么就建⼀条Ax连向By的边。

　图中有多少条路径，可以以⼀种⽅法得到，就是计算出度为0的点的个数。

如果知道这个就很容易得出这个结论了　·最⼩相交路径覆盖　做法⾸先跑floyd，求出原图的传递闭包，然后⽤上述⽅法做即可③最⼩边覆盖最⼩边覆盖=图顶点-最⼤匹配⾸先⼀开始，假如⼀条边都不选的话，要覆盖所有的点就必须每个点都选⼀次，也就是n次，然后每选⼀条边就会减少1个，所以结论显⽽易见④最⼤独⽴集最⼤独⽴集=图顶点-最⼤匹配=最⼩边覆盖⼆分图的独⽴数等于顶点数减去最⼤匹配数，很显然的把最⼤匹配两端的点都从顶点集中去掉这个时候剩余的点是独⽴集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取⼀个点加⼊独⽴集并且保持其独⽴集性质。

⼆分图多重匹配( ⼀ ) 如果x部节点只对应⼀个y部节点,⽽y部节点可以对应多个x部节点,那么这种匹配可以⽤匈⽛利算法来解决解决的问题：⼀个y最多匹配cnt个x是否成⽴，要问⼀个y匹配⼈数最⼤的最⼩值可以⽤⼆分答案来做解决思路：根据匈⽛利算法的思想，这时的link[u]要变成link[u][i],表⽰与y[u]匹配好了的第i个点，⽤vlink[u]记录已经于u点匹配了的点的个数，对于x中的x[k],找到⼀个与他相连的y[i]后，同样判断匈⽛利算法中的两个条件是否成⽴，若满⾜第⼀个条件，直接将x[k]，y[i]匹配，否则，如果与y[i]所匹配的点已经达到了饱和，那么在所有与y[i]配合的点中选⼀个点，检查能否找到增⼴路，如果能，就让出位置让x[k]与y[i]匹配( ⼆ )如果x部节点可以匹配多个y部节点,y部节点可以同时匹配多个x部节点,那么应该⽤⽹络流来解决。

⼆分图最⼤匹配总结⼆分图匹配（匈⽛利算法）1。

⼀个⼆分图中的最⼤匹配数等于这个图中的最⼩点覆盖数König定理是⼀个⼆分图中很重要的定理，它的意思是，⼀个⼆分图中的最⼤匹配数等于这个图中的最⼩点覆盖数。

如果你还不知道什么是最⼩点覆盖，我也在这⾥说⼀下：假如选了⼀个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。

2。

最⼩路径覆盖=最⼩路径覆盖＝｜G｜－最⼤匹配数在⼀个N*N的有向图中，路径覆盖就是在图中找⼀些路经，使之覆盖了图中的所有顶点，且任何⼀个顶点有且只有⼀条路径与之关联；（如果把这些路径中的每条路径从它的起始点⾛到它的终点，那么恰好可以经过图中的每个顶点⼀次且仅⼀次）；如果不考虑图中存在回路，那么每每条路径就是⼀个弱连通⼦集．由上⾯可以得出：1.⼀个单独的顶点是⼀条路径；2.如果存在⼀路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．最⼩路径覆盖就是找出最⼩的路径条数，使之成为G的⼀个路径覆盖．路径覆盖与⼆分图匹配的关系：最⼩路径覆盖＝｜G｜－最⼤匹配数；3。

⼆分图最⼤独⽴集=顶点数-⼆分图最⼤匹配独⽴集：图中任意两个顶点都不相连的顶点集合。

⼆分图模板：模板⼀：匈⽛利算法/* **************************************************************************//⼆分图匹配（匈⽛利算法的DFS实现）//初始化：g[][]两边顶点的划分情况//建⽴g[i][j]表⽰i->j的有向边就可以了，是左边向右边的匹配//g没有边相连则初始化为0//uN是匹配左边的顶点数，vN是匹配右边的顶点数//调⽤：res=hungary();输出最⼤匹配数//优点：适⽤于稠密图，DFS找增⼴路，实现简洁易于理解//时间复杂度:O(VE)//***************************************************************************///顶点编号从0开始的const int MAXN=510;int uN,vN;//u,v数⽬int g[MAXN][MAXN];int linker[MAXN];bool used[MAXN];bool dfs(int u)//从左边开始找增⼴路径{int v;for(v=0;v<vN;v++)//这个顶点编号从0开始，若要从1开始需要修改if(g[u][v]&&!used[v]){used[v]=true;if(linker[v]==-1||dfs(linker[v])){//找增⼴路，反向linker[v]=u;return true;}}return false;//这个不要忘了，经常忘记这句}int hungary(){int res=0;int u;memset(linker,-1,sizeof(linker));for(u=0;u<uN;u++){memset(used,0,sizeof(used));if(dfs(u)) res++;}return res;}//******************************************************************************/模板⼆： Hopcroft-Carp算法这个算法⽐匈⽛利算法的时间复杂度要⼩，⼤数据可以采⽤这个算法/* *********************************************⼆分图匹配（Hopcroft-Carp的算法）。