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

什么是二分图与最大匹配？

二分图（Bipartite Graph）是一种特殊的图结构，其顶点可以分为两个互不相交的集合 U 和 V，图中的每条边都连接 U 中的一个顶点和 V 中的一个顶点。

最大匹配是指在二分图中选择尽可能多的边，使得任意两条边没有公共顶点。例如：有 3 个工人和 3 个任务，每个工人只能做某些任务，我们希望安排最多的人去做他们能做的任务——这就是一个典型的最大匹配问题。

匈牙利算法的核心思想

匈牙利算法通过不断寻找增广路径（Augmenting Path）来扩大当前匹配的大小。如果找不到增广路径，则当前匹配就是最大匹配。

简单来说，算法会尝试为每个未匹配的左部节点（如工人）找到一个右部节点（如任务），如果该任务已被占用，则尝试“腾出”位置——递归地为原占用者找新任务，直到成功或失败。

Rust 实现步骤详解

我们将使用邻接表表示图，并通过 DFS（深度优先搜索）寻找增广路径。

1. 定义图结构

假设左部有 n 个节点（编号 0 到 n-1），右部有 m 个节点（编号 0 到 m-1）。我们用 graph[i] 表示左部节点 i 可以连接的所有右部节点。

// graph[i] = [j1, j2, ...] 表示左部节点 i 可以匹配右部节点 j1, j2, ...let graph: Vec<Vec<usize>> = vec![    vec![0, 1],     // 工人0可以做任务0和1    vec![1, 2],     // 工人1可以做任务1和2    vec![2]         // 工人2只能做任务2];

2. 实现匈牙利算法函数

我们需要一个 match_r 数组记录右部每个节点匹配的左部节点（-1 表示未匹配），以及一个 visited 数组防止重复访问。

fn dfs(    u: usize,    graph: &Vec<Vec<usize>>,    match_r: &mut Vec<i32>,    visited: &mut Vec<bool>) -> bool {    for &v in &graph[u] {        if visited[v] {            continue;        }        visited[v] = true;        // 如果右部节点 v 未匹配，或已匹配但能为原匹配者找到新任务        if match_r[v] == -1 || dfs(match_r[v] as usize, graph, match_r, visited) {            match_r[v] = u as i32;            return true;        }    }    false}fn hungarian(graph: &Vec<Vec<usize>>, m: usize) -> usize {    let mut match_r = vec![-1; m]; // 右部每个节点的匹配对象    let mut result = 0;    for u in 0..graph.len() {        let mut visited = vec![false; m];        if dfs(u, graph, &mut match_r, &mut visited) {            result += 1;        }    }    result}

3. 主函数调用示例

fn main() {    let graph = vec![        vec![0, 1],        vec![1, 2],        vec![2]    ];    let m = 3; // 右部节点数量（任务数）    let max_matching = hungarian(&graph, m);    println!("最大匹配数: {}", max_matching); // 输出: 3}

关键点解析

• Rust 所有权机制：我们在函数参数中使用 & 引用避免数据拷贝，提高效率。
• 类型安全：使用 i32 存储匹配结果（因为 -1 表示未匹配），而索引用 usize，注意类型转换。
• DFS 递归：每次尝试为一个左部节点找匹配时，都要重置 visited 数组。

总结

通过本教程，你已经学会了如何用 Rust 实现 匈牙利算法 来解决 二分图最大匹配 问题。这项技能在算法竞赛、任务调度系统、资源分配等场景中非常实用。

记住，理解算法背后的逻辑比死记代码更重要。建议你动手修改图结构，观察输出变化，加深理解。

如果你正在学习 Rust 教程 或准备面试，不妨将此代码加入你的算法模板库！

© 2023 Rust 算法学习指南 | 掌握核心算法，构建高效系统