用 Rust 构建图结构（邻接矩阵表示法从零入门）

什么是邻接矩阵？

邻接矩阵是一种用二维数组（或向量）来表示图中顶点之间连接关系的方法。假设图中有 n 个顶点，那么我们就创建一个 n × n 的矩阵。如果顶点 i 和顶点 j 之间存在一条边，那么矩阵中第 i 行第 j 列的值就为 true（或权重值，如果是带权图）；否则为 false（或 0）。

这种表示法特别适合稠密图（即边数接近顶点数平方的图），因为无论图是否稀疏，它都需要占用 O(n²) 的空间。

在 Rust 中实现邻接矩阵

Rust 是一种内存安全、高性能的系统编程语言。我们可以利用其强大的类型系统和所有权机制，安全地构建图结构。

下面是一个简单的无向、无权图的邻接矩阵实现：

// 定义图结构体struct Graph {    size: usize,    matrix: Vec<Vec<bool>>,}impl Graph {    // 创建一个新图    fn new(n: usize) -> Self {        let mut matrix = vec![vec![false; n]; n];        Graph { size: n, matrix }    }    // 添加边（无向图）    fn add_edge(&mut self, u: usize, v: usize) {        if u < self.size && v < self.size {            self.matrix[u][v] = true;            self.matrix[v][u] = true; // 无向图对称        }    }    // 检查是否存在边    fn has_edge(&self, u: usize, v: usize) -> bool {        if u < self.size && v < self.size {            self.matrix[u][v]        } else {            false        }    }    // 打印邻接矩阵（用于调试）    fn print_matrix(&self) {        for row in &self.matrix {            println!("{:?}", row);        }    }}fn main() {    let mut g = Graph::new(4); // 创建4个顶点的图    g.add_edge(0, 1);    g.add_edge(1, 2);    g.add_edge(2, 3);    g.add_edge(0, 3);    println!("邻接矩阵:");    g.print_matrix();    println!("\n顶点0和2之间是否有边？{}", g.has_edge(0, 2));}

代码解析

• 结构体定义：我们用 size 记录顶点数量，matrix 是一个二维布尔向量，代表邻接矩阵。
• new 方法：初始化一个 n×n 的全 false 矩阵。
• add_edge：添加一条无向边，因此需要同时设置 [u][v] 和 [v][u] 为 true。
• 边界检查：所有操作都检查索引是否越界，避免 panic，这是 Rust 安全性的体现。

邻接矩阵的优缺点

优点：

• 查询两个顶点是否相连的时间复杂度是 O(1)，非常快。
• 实现简单直观，适合教学和小规模图。

缺点：

• 空间复杂度高（O(n²)），对于稀疏图（边很少）会浪费大量内存。
• 遍历某个顶点的所有邻居需要扫描整行，时间复杂度为 O(n)。

总结

通过本教程，你已经学会了如何在 Rust 中使用邻接矩阵表示图。这是学习更复杂图算法（如 BFS、DFS、Dijkstra 等）的基础。虽然邻接矩阵在处理大规模稀疏图时效率不高，但它在概念上非常清晰，是理解图结构的良好起点。

掌握 Rust邻接矩阵、图的表示方法、Rust数据结构 和 邻接矩阵实现 这些核心概念后，你可以进一步探索邻接表等更高效的图表示方式。

Happy Coding with Rust! 🦀