Rust语言实现图的邻接表表示法（小白也能看懂的图数据结构教程）

相比邻接矩阵，邻接表在存储稀疏图时能显著节省内存空间，并且遍历邻居节点的效率更高。这也是为什么在实际工程中，Rust图算法通常优先采用邻接表。

在 Rust 中实现邻接表

Rust 提供了强大的所有权和内存安全机制，非常适合构建高效的数据结构。我们可以使用 Vec<Vec<usize>> 来表示一个无权无向图的邻接表。

1. 基础结构定义

struct Graph {    adjacency_list: Vec<Vec<usize>>,    vertex_count: usize,}

2. 构造函数

impl Graph {    fn new(vertex_count: usize) -> Self {        let mut adjacency_list = Vec::with_capacity(vertex_count);        for _ in 0..vertex_count {            adjacency_list.push(Vec::new());        }        Graph {            adjacency_list,            vertex_count,        }    }}

3. 添加边（无向图）

impl Graph {    // ... 其他方法 ...    fn add_edge(&mut self, u: usize, v: usize) {        // 确保顶点索引有效        if u >= self.vertex_count || v >= self.vertex_count {            panic!("Vertex index out of bounds!");        }        self.adjacency_list[u].push(v);        self.adjacency_list[v].push(u); // 无向图：双向添加    }}

4. 完整示例：创建并打印图

fn main() {    // 创建一个包含 5 个顶点的图    let mut graph = Graph::new(5);    // 添加边    graph.add_edge(0, 1);    graph.add_edge(0, 4);    graph.add_edge(1, 2);    graph.add_edge(1, 3);    graph.add_edge(1, 4);    graph.add_edge(2, 3);    graph.add_edge(3, 4);    // 打印邻接表    for (i, neighbors) in graph.adjacency_list.iter().enumerate() {        println!("顶点 {}: {:?}", i, neighbors);    }}

运行上述代码，你将看到如下输出：

顶点 0: [1, 4]顶点 1: [0, 2, 3, 4]顶点 2: [1, 3]顶点 3: [1, 2, 4]顶点 4: [0, 1, 3]

扩展：有向图与带权图

上面的例子是无向无权图。如果你需要处理有向图，只需在 add_edge 中只执行 self.adjacency_list[u].push(v) 即可。

对于带权图，可以将邻接表改为 Vec<Vec<(usize, i32)>>，其中元组的第二个元素表示边的权重：

// 带权有向图示例struct WeightedGraph {    adjacency_list: Vec<Vec<(usize, i32)>>,    vertex_count: usize,}impl WeightedGraph {    fn new(vertex_count: usize) -> Self {        WeightedGraph {            adjacency_list: vec![Vec::new(); vertex_count],            vertex_count,        }    }    fn add_edge(&mut self, u: usize, v: usize, weight: i32) {        if u >= self.vertex_count || v >= self.vertex_count {            panic!("Vertex index out of bounds!");        }        self.adjacency_list[u].push((v, weight));    }}

总结

通过本教程，你已经掌握了如何在 Rust 中使用邻接表来表示图。这种表示方法不仅节省内存，而且便于遍历邻居节点，是实现各种 Rust图算法（如深度优先搜索 DFS、广度优先搜索 BFS、Dijkstra 最短路径等）的基础。

记住，理解 Rust邻接表 是掌握更复杂 Rust数据结构 和算法的第一步。动手实践，尝试修改代码以支持不同类型的图，你会对 Rust 的所有权系统和性能优势有更深的体会！

关键词回顾：Rust邻接表、图的表示方法、Rust图算法、Rust数据结构