用Rust实现Kruskal算法（手把手教你构建最小生成树）

什么是Kruskal算法？

Kruskal算法的核心思想是：按边的权重从小到大排序，依次选择边加入生成树，但要确保不会形成环。为了高效判断是否成环，通常配合并查集（Union-Find）数据结构。

该算法的时间复杂度主要由排序决定，为 O(E log E)，其中 E 是边的数量。对于稀疏图来说，效率非常高。

Rust实现步骤概览

1. 定义图的边结构（包含起点、终点和权重）
2. 实现并查集（Union-Find）结构
3. 对边按权重排序
4. 遍历排序后的边，使用并查集避免环，构建最小生成树

第1步：定义边结构

首先，我们定义一个 Edge 结构体来表示图中的每一条边：

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

第2步：实现并查集（Union-Find）

并查集用于高效判断两个顶点是否属于同一连通分量，从而避免环的产生。以下是Rust中的实现：

struct UnionFind {    parent: Vec,    rank: Vec,}impl UnionFind {    fn new(n: usize) -> Self {        let mut parent = vec![0; n];        for i in 0..n {            parent[i] = i;        }        UnionFind {            parent,            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    }}

第3步：实现Kruskal算法主函数

现在我们将上述组件组合起来，编写Kruskal算法的主逻辑：

fn kruskal(n: usize, edges: &mut [Edge]) -> Vec {    // 按权重升序排序    edges.sort_by_key(|e| e.weight);    let mut uf = UnionFind::new(n);    let mut mst = Vec::new();    for edge in edges.iter() {        if uf.union(edge.src, edge.dst) {            mst.push(edge.clone());            if mst.len() == n - 1 {                break; // 最小生成树已有 n-1 条边            }        }    }    mst}

第4步：完整示例与测试

下面是一个完整的可运行示例，展示如何使用上述代码求解最小生成树：

fn main() {    let mut edges = vec![        Edge { src: 0, dst: 1, weight: 10 },        Edge { src: 0, dst: 2, weight: 6 },        Edge { src: 0, dst: 3, weight: 5 },        Edge { src: 1, dst: 3, weight: 15 },        Edge { src: 2, dst: 3, weight: 4 },    ];    let n = 4; // 顶点数量    let mst = kruskal(n, &mut edges);    println!("最小生成树的边:");    for edge in &mst {        println!("({} - {}) weight: {}", edge.src, edge.dst, edge.weight);    }    let total_weight: i32 = mst.iter().map(|e| e.weight).sum();    println!("总权重: {}", total_weight);}

运行结果将输出最小生成树的边及其总权重。你可以尝试修改输入边，观察不同图的最小生成树变化。

总结

通过本教程，你已经学会了如何在Rust中实现Kruskal算法来求解最小生成树。关键点包括：边的排序、并查集的路径压缩与按秩合并优化。这种实现方式不仅高效，而且充分利用了Rust的内存安全特性。

掌握Rust图算法和Rust并查集实现后，你可以进一步探索Prim算法、Dijkstra最短路径等更复杂的图论问题。希望这篇教程对你有所帮助！