用Rust构建高效网络：最小生成树算法详解（小白也能学会的Rust图论实战）

注意：一棵生成树必须包含图中所有顶点，但不能有环，且边数 = 顶点数 - 1。

准备工作：Rust 图的表示

在开始算法前，我们需要一种方式来表示图。最常用的是邻接表或边列表。对于 Prim 算法，邻接表更高效；对于 Kruskal，边列表更合适。

首先，定义一条边：

#[derive(Debug, Clone)]struct Edge {    u: usize,    v: usize,    weight: i32,}

方法一：Prim 算法（贪心 + 优先队列）

Prim 算法从一个起始顶点开始，每次选择连接已选顶点集和未选顶点集中权重最小的边，直到覆盖所有顶点。

我们需要使用 BinaryHeap（最大堆），但 Rust 默认是最大堆，因此我们将权重取负来模拟最小堆。

use std::collections::{BinaryHeap, HashSet};fn prim_mst(n: usize, edges: &Vec<(usize, usize, i32)>) -> Vec<Edge> {    // 构建邻接表    let mut graph = vec![vec![]; n];    for &(u, v, w) in edges {        graph[u].push((v, w));        graph[v].push((u, w));    }    let mut visited = HashSet::new();    let mut heap = BinaryHeap::new();    let mut mst = Vec::new();    // 从顶点0开始    visited.insert(0);    for &(neighbor, weight) in &graph[0] {        heap.push((-weight, 0, neighbor));    }    while let Some((neg_w, u, v)) = heap.pop() {        let weight = -neg_w;        if visited.contains(&v) {            continue;        }        visited.insert(v);        mst.push(Edge { u, v, weight });        for &(neighbor, w) in &graph[v] {            if !visited.contains(&neighbor) {                heap.push((-w, v, neighbor));            }        }    }    mst}

方法二：Kruskal 算法（排序 + 并查集）

Kruskal 算法则先将所有边按权重从小到大排序，然后依次选取边，只要不形成环就加入生成树。判断是否成环需要用到并查集（Union-Find）数据结构。

首先实现一个简单的并查集：

struct UnionFind {    parent: Vec<usize>,    rank: Vec<usize>,}impl UnionFind {    fn new(n: usize) -> Self {        UnionFind {            parent: (0..n).collect(),            rank: vec![0; n],        }    }    fn find(&mut self, x: usize) -> usize {        if self.parent[x] != x {            self.parent[x] = self.find(self.parent[x]);        }        self.parent[x]    }    fn union(&mut self, x: usize, y: usize) -> bool {        let root_x = self.find(x);        let root_y = self.find(y);        if root_x == root_y {            return false; // 已在同一集合，会成环        }        if self.rank[root_x] < self.rank[root_y] {            self.parent[root_x] = root_y;        } else if self.rank[root_x] > self.rank[root_y] {            self.parent[root_y] = root_x;        } else {            self.parent[root_y] = root_x;            self.rank[root_x] += 1;        }        true    }}

然后实现 Kruskal 算法：

fn kruskal_mst(n: usize, edges: &mut Vec<Edge>) -> Vec<Edge> {    // 按权重升序排序    edges.sort_by_key(|e| e.weight);    let mut uf = UnionFind::new(n);    let mut mst = Vec::new();    for edge in edges {        if uf.union(edge.u, edge.v) {            mst.push(edge.clone());            if mst.len() == n - 1 {                break;            }        }    }    mst}

完整示例与测试

下面是一个完整的可运行示例：

fn main() {    let n = 4;    let mut edges = vec![        Edge { u: 0, v: 1, weight: 10 },        Edge { u: 0, v: 2, weight: 6 },        Edge { u: 0, v: 3, weight: 5 },        Edge { u: 1, v: 3, weight: 15 },        Edge { u: 2, v: 3, weight: 4 },    ];    println!("=== Kruskal 算法结果 ===");    let mst_kruskal = kruskal_mst(n, &mut edges.clone());    for e in &mst_kruskal {        println!("{} - {} : {}", e.u, e.v, e.weight);    }    // 转换为元组用于 Prim    let edge_tuples: Vec<(usize, usize, i32)> = edges        .iter()        .map(|e| (e.u, e.v, e.weight))        .collect();    println!("\n=== Prim 算法结果 ===");    let mst_prim = prim_mst(n, &edge_tuples);    for e in &mst_prim {        println!("{} - {} : {}", e.u, e.v, e.weight);    }}

总结

通过本教程，我们学习了如何在 Rust 中实现 Rust最小生成树 的两种经典算法。Prim 算法适合稠密图，时间复杂度为 O(E log V)；Kruskal 算法适合稀疏图，时间复杂度为 O(E log E)。两者都充分利用了 Rust 的内存安全和高性能特性。

无论你是想深入理解 Rust图算法，还是准备面试题，掌握 Prim算法Rust实现 和 Kruskal算法Rust教程 都是非常有价值的技能。动手试试吧！

提示：你可以将上述代码保存为 mst.rs 并用 cargo run 运行，确保你的 Rust 环境已安装。