Rust语言实现最小生成树算法（从零开始掌握图论经典算法）

为什么选择Rust实现图算法？

Rust以其内存安全、零成本抽象和高性能著称，非常适合实现系统级算法。使用Rust编写Rust图算法不仅能保证程序的正确性，还能获得接近C/C++的执行效率。

准备工作：定义图的数据结构

在实现算法前，我们先定义一个简单的带权无向图结构：

// 定义边结构体#[derive(Clone, Debug)]struct Edge {    src: usize,    dest: usize,    weight: i32,}// 定义图结构体struct Graph {    vertices: usize,    edges: Vec<Edge>,    // 邻接表表示（用于Prim算法）    adj_list: Vec<Vec<(usize, i32)>>,}impl Graph {    fn new(vertices: usize) -> Self {        Graph {            vertices,            edges: Vec::new(),            adj_list: vec![Vec::new(); vertices],        }    }    fn add_edge(&mut self, src: usize, dest: usize, weight: i32) {        // 无向图：双向添加        self.adj_list[src].push((dest, weight));        self.adj_list[dest].push((src, weight));        self.edges.push(Edge { src, dest, weight });    }}

Prim算法：贪心策略构建MST

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

use std::collections::BinaryHeap;use std::cmp::Reverse;fn prim_mst(graph: &Graph) -> Vec<Edge> {    let mut mst = Vec::new();    let mut visited = vec![false; graph.vertices];    let mut min_heap: BinaryHeap<Reverse<(i32, usize, usize)>> = BinaryHeap::new();    // 从顶点0开始    visited[0] = true;    for &(neighbor, weight) in &graph.adj_list[0] {        min_heap.push(Reverse((weight, 0, neighbor)));    }    while let Some(Reverse((weight, u, v))) = min_heap.pop() {        if visited[v] {            continue;        }        visited[v] = true;        mst.push(Edge {            src: u,            dest: v,            weight,        });        // 将新顶点的邻边加入堆        for &(neighbor, w) in &graph.adj_list[v] {            if !visited[neighbor] {                min_heap.push(Reverse((w, v, neighbor)));            }        }    }    mst}

Kruskal算法：基于并查集的全局最优

Kruskal算法按边的权重从小到大排序，依次选择边，如果该边不会形成环就加入MST。这里我们需要实现一个并查集（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    }}fn kruskal_mst(graph: &Graph) -> Vec<Edge> {    let mut edges = graph.edges.clone();    // 按权重升序排序    edges.sort_by_key(|e| e.weight);    let mut uf = UnionFind::new(graph.vertices);    let mut mst = Vec::new();    for edge in edges {        if uf.union(edge.src, edge.dest) {            mst.push(edge);            if mst.len() == graph.vertices - 1 {                break;            }        }    }    mst}

完整示例与测试

现在我们将所有代码整合，并测试一个简单图：

fn main() {    // 创建一个5个顶点的图    let mut graph = Graph::new(5);    graph.add_edge(0, 1, 2);    graph.add_edge(0, 3, 6);    graph.add_edge(1, 2, 3);    graph.add_edge(1, 3, 8);    graph.add_edge(1, 4, 5);    graph.add_edge(2, 4, 7);    graph.add_edge(3, 4, 9);    println!("Prim算法结果:");    let prim_result = prim_mst(&graph);    for edge in &prim_result {        println!("{} - {} : {}", edge.src, edge.dest, edge.weight);    }    println!("\nKruskal算法结果:");    let kruskal_result = kruskal_mst(&graph);    for edge in &kruskal_result {        println!("{} - {} : {}", edge.src, edge.dest, edge.weight);    }}

总结

通过本教程，你已经掌握了如何用Rust实现Rust最小生成树算法。Prim算法适合稠密图，时间复杂度为O(E log V)；Kruskal算法适合稀疏图，时间复杂度为O(E log E)。两种方法各有优势，可根据实际场景选择。

学习Prim算法Rust实现和Kruskal算法Rust教程不仅能加深你对图论的理解，还能提升Rust编程能力。建议你尝试修改代码，处理不同规模的图，甚至优化性能！

希望这篇教程对你有帮助。Happy coding with Rust!