KM算法详解（Python语言实现二分图最大权匹配）

KM算法的核心思想

KM算法通过维护两个“顶标”（label）数组 lx 和 ly，使得对于任意边 (i, j)，都有 lx[i] + ly[j] >= weight[i][j]。当等号成立时，这条边称为“可行边”。算法的目标是找到一个由可行边构成的完美匹配。

如果当前可行边无法构成完美匹配，就调整顶标，扩大可行边集合，直到找到完美匹配为止。

Python实现步骤详解

下面我们一步步用 Python 实现 KM 算法。假设我们有一个 n×n 的权重矩阵 w，表示工人 i 做任务 j 的收益。

1. 初始化顶标

对左侧每个点 i，令 lx[i] = max(w[i])；右侧每个点 j，令 ly[j] = 0。

2. 匈牙利算法找增广路

使用 DFS 或 BFS 在可行边构成的子图中尝试寻找增广路径。

3. 调整顶标

若找不到增广路，则计算最小 slack 值，并更新顶标，使更多边变为可行边。

完整Python代码实现

def km_algorithm(w):    """    KM算法求解二分图最大权完美匹配    :param w: n x n 的权重矩阵    :return: (匹配结果match, 最大总权重)    """    n = len(w)    lx = [max(row) for row in w]  # 左侧顶标    ly = [0] * n                  # 右侧顶标    match = [-1] * n              # match[j] = i 表示任务j分配给工人i    def dfs(u, vx, vy, slack):        vx[u] = True        for v in range(n):            if vy[v]:                continue            gap = lx[u] + ly[v] - w[u][v]            if gap == 0:                vy[v] = True                if match[v] == -1 or dfs(match[v], vx, vy, slack):                    match[v] = u                    return True            else:                slack[v] = min(slack[v], gap)        return False    for u in range(n):        while True:            vx = [False] * n            vy = [False] * n            slack = [float('inf')] * n            if dfs(u, vx, vy, slack):                break            # 更新顶标            delta = min(slack[v] for v in range(n) if not vy[v])            for i in range(n):                if vx[i]:                    lx[i] -= delta                if vy[i]:                    ly[i] += delta        total_weight = sum(w[match[j]][j] for j in range(n))    return match, total_weight# 示例使用if __name__ == "__main__":    weights = [        [3, 5, 2],        [4, 1, 6],        [2, 7, 3]    ]    match, total = km_algorithm(weights)    print("匹配结果（任务 -> 工人）:", match)    print("最大总权重:", total)

代码说明

• lx 和 ly 是左右两侧的顶标。
• match 数组记录任务 j 被分配给哪个工人。
• dfs 函数尝试从工人 u 出发寻找增广路径。
• 如果找不到，就用 slack 计算最小调整量 delta，更新顶标。

总结

通过本教程，你已经掌握了 KM算法 的基本原理和 Python实现KM算法 的完整过程。该算法适用于解决二分图最大权匹配问题，在任务分配、资源调度等领域有广泛应用。

记住，KM算法要求二分图是完全二分图（即左右节点数相等且存在完美匹配）。如果实际问题不满足，可通过添加虚拟节点和零权重边进行转换。

希望这篇教程能帮助你理解这一经典算法！如果你觉得有用，不妨动手运行代码，修改权重矩阵，观察匹配结果的变化。