当前位置：首页 > Rust > 正文

Rust语言KM算法实现（从零开始掌握二分图最大权匹配）

主机测评网
Rust
2025-12-10
332

在计算机科学中，KM算法（Kuhn-Munkres Algorithm），也被称为匈牙利算法的加权版本，用于解决二分图最大权完美匹配问题。本文将带你用Rust语言一步步实现KM算法，即使你是编程小白，也能轻松理解！

Rust语言KM算法实现（从零开始掌握二分图最大权匹配） Rust KM算法匈牙利算法 Rust实现二分图最大权匹配 Rust图论算法第1张

什么是KM算法？

KM算法用于在一个完全二分图中找到一组边，使得每个左部节点和右部节点恰好被匹配一次，并且所有匹配边的权重之和最大。这在任务分配、资源调度等场景中非常有用。

例如：有3个工人和3个任务，每个工人完成不同任务有不同的收益，如何分配才能使总收益最大？这就是KM算法的经典应用场景。

前置知识

基本的Rust语法（变量、循环、函数）
对二分图有初步了解
理解“匹配”和“权重”的概念

算法核心思想

KM算法通过维护两个顶标（label）数组 lx 和 ly，使得对于任意边 (i, j)，满足：

  lx[i] + ly[j] ≥ weight[i][j]

当等号成立时，这条边称为“可行边”。算法的目标是找到一个由可行边构成的完美匹配。

Rust实现步骤详解

我们将实现一个函数 km_algorithm，输入是一个二维权重矩阵，输出是最大权匹配结果。

1. 初始化数据结构

fn km_algorithm(weight: &Vec<Vec<i32>>) -> (i32, Vec<usize>) {    let n = weight.len();    let mut lx = vec![0i32; n];    let mut ly = vec![0i32; n];    let mut match_y = vec![usize::MAX; n]; // 右侧节点匹配的左侧节点    // 初始化左顶标为每行最大值    for i in 0..n {        lx[i] = *weight[i].iter().max().unwrap();    }    // ... 后续逻辑}

2. 匈牙利树搜索（DFS辅助）

对每个左侧节点，尝试寻找增广路径：

fn dfs(    x: usize,    weight: &Vec<Vec<i32>>,    lx: &Vec<i32>,    ly: &Vec<i32>,    slack: &mut Vec<i32>,    vx: &mut Vec<bool>,    vy: &mut Vec<bool>,    match_y: &mut Vec<usize>,) -> bool {    vx[x] = true;    let n = weight.len();    for y in 0..n {        if vy[y] {            continue;        }        let gap = lx[x] + ly[y] - weight[x][y];        if gap == 0 {            vy[y] = true;            if match_y[y] == usize::MAX || dfs(match_y[y], weight, lx, ly, slack, vx, vy, match_y) {                match_y[y] = x;                return true;            }        } else {            slack[y] = slack[y].min(gap);        }    }    false}

3. 主循环：调整顶标直到找到完美匹配

// 在 km_algorithm 函数中继续for root in 0..n {    let mut slack = vec![i32::MAX; n];    loop {        let mut vx = vec![false; n];        let mut vy = vec![false; n];        if dfs(root, weight, &lx, &ly, &mut slack, &mut vx, &mut vy, &mut match_y) {            break;        }        // 更新顶标        let delta = slack.iter()            .enumerate()            .filter(|&(i, _)| !vy[i])            .map(|(_, &s)| s)            .min()            .unwrap();        for i in 0..n {            if vx[i] {                lx[i] -= delta;            }            if vy[i] {                ly[i] += delta;            } else {                slack[i] -= delta;            }        }    }}

4. 计算结果并返回

// 计算最大权重和let mut total_weight = 0;for y in 0..n {    total_weight += weight[match_y[y]][y];}(total_weight, match_y)

完整代码示例

将上述片段整合，你将得到一个完整的KM算法实现。下面是一个测试用例：

fn main() {    let weight = vec![        vec![3, 2, 1],        vec![2, 4, 3],        vec![1, 3, 5],    ];    let (max_weight, matching) = km_algorithm(&weight);    println!("最大权重和: {}", max_weight);    for (y, &x) in matching.iter().enumerate() {        println!("工人 {} 被分配任务 {}", x, y);    }}