图的顶点恰好可以分成两个集合，同一个集合内的顶点间不允许有边，处在不同集合的顶点允许有边相连。
增广路（augmenting path）：假设目前已有一个匹配结果，存在一组未匹配定点的OD，能够找到一条路径，这条路径上匹配和未匹配的定点交替出现，称为增广路
增广路上的匹配和未匹配取反，则匹配数增加1。
基本思想：通过引入顶标，将最优权值匹配转化为最大匹配问题。
步骤1：将边权值转化为顶标/标杆，一般来讲，初始化时，X集合的元素取对应权重的最大值，Y集合的元素取0。取出满足以下条件的边，构建二分图：weight(i,j) = label(i) + label(j)；该二分图称为相等子图
步骤2：寻找增广路，从X0开始，找到X0Y4；在X1，找不到增广路，需要调整顶标，扩大相等子图；当找不到增广路径时，对于搜索过的路径上的XY点，设该路径上的X顶点集为S，Y顶点集为T，对所有在S中的点xi及不在T中的点yj，计算d=min{(L(xi)+L(yj)-weight(xiyj))}，从S集中的X标杆中减去d，并将其加入到T集中的Y的标杆中；本例寻找增广路的过程中，访问了X1、Y4、X0三个节点，因此对应的边是X1Y0，d为2（从贪心选边的角度看，我们可以为X0选择新的边而抛弃原先的二分子图中的匹配边，也可以为X1选择新的边而抛弃原先的二分子图中的匹配边，因为我们不能同时选择X0Y4和X1Y4，因为这是一个不合法匹配，这个时候，d=min{(L(xi)+L(yj)-weight(xiyj))}的意义就在于，我们选择一条新的边，这条边将被加入匹配子图中使得匹配合法，选择这条边形成的匹配子图，将比原先的匹配子图加上这条非法边组成的非法匹配子图的权重和（如果它是合法的，它将是最大的）小最少，即权重最大了）；此时再次为X1寻找增广路，得到X1Y0.
步骤3：对X2寻找增广路，搜索范围如上图蓝色路径所示，找不到增广路，需要扩大相等子图；按照步骤2同一规则，会将边X0Y2、X2Y1加入，d=1.
步骤4：在新的相等子图上，对X2重新寻找增广路。如果是深度优先，得到的路线是X2Y0->Y0X1->X1Y4->Y4X0->X0Y2，此时将匹配结果取反，则得到X2Y0、X1Y4、X0Y2三个匹配；如果是宽度优先，得到的匹配结果是X0Y4、X1Y0、X2Y1，如下图：
Python实现
import numpy as np
# 声明数据结构
adj_matrix = build_graph() # np array with dimension N*N
# 初始化顶标
label_left = np.max(adj_matrix, axis=1) # init label for the left set
label_right = np.zeros(N) # init label for the right set
# 初始化匹配结果
match_right = np.empty(N) * np.nan
# 初始化辅助变量
visit_left = np.empty(N) * False
visit_right = np.empty(N) * False
slack_right = np.empty(N) * np.inf
# 寻找增广路，深度优先
def find_path(i):
visit_left[i] = True
for j, match_weight in enumerate(adj_matrix[i]):
if visit_right[j]: continue # 已被匹配（解决递归中的冲突）
gap = label_left[i] + label_right[j] - match_weight
if gap == 0:
# 找到可行匹配
visit_right[j] = True
if np.isnan(match_right[j]) or find_path(match_right[j]): ## j未被匹配，或虽然j已被匹配，但是j的已匹配对象有其他可选备胎
match_right[j] = i
return True
else:
# 计算变为可行匹配需要的顶标改变量
if slack_right[j] < gap: slack_right[j] = gap
return False
# KM主函数
def KM():
for i in range(N):
# 重置辅助变量
slack_right = np.empty(N) * np.inf
while True:
# 重置辅助变量
visit_left = np.empty(N) * False
visit_right = np.empty(N) * False
# 能找到可行匹配
if find_path(i): break
# 不能找到可行匹配，修改顶标
# (1)将所有在增广路中的X方点的label全部减去一个常数d
# (2)将所有在增广路中的Y方点的label全部加上一个常数d
d = np.inf
for j, slack in enumerate(slack_right):
if not visit_right[j] and slack < d:
d = slack
for k in range(N):
if visit_left[k]: label_left[k] -= d
for n in range(N):
if visit_right[n]: label_right[n] += d
res = 0
for j in range(N):
if match_right[j] >=0 and match_right[j] < N:
res += adj_matrix[match[j]][j]
return reshttp://blog.sina.com.cn/s/blo...
https://blog.csdn.net/mosquit...