Rust语言图的表示方法实现（从零开始掌握Rust中的图数据结构）

Rust图表示方法一：邻接矩阵（Adjacency Matrix）

邻接矩阵使用二维数组来表示图。如果节点 i 和节点 j 之间有边，则 matrix[i][j] = 1（或权重值），否则为 0。

优点：查询两个节点是否相连的时间复杂度为 O(1)。
缺点：空间复杂度高，为 O(V²)，其中 V 是节点数。

// 使用 Vec<Vec<bool>> 表示无权无向图struct GraphMatrix {    adj_matrix: Vec<Vec<bool>>,    vertex_count: usize,}impl GraphMatrix {    fn new(n: usize) -> Self {        let mut matrix = vec![vec![false; n]; n];        GraphMatrix {            adj_matrix: matrix,            vertex_count: n,        }    }    fn add_edge(&mut self, u: usize, v: usize) {        if u < self.vertex_count && v < self.vertex_count {            self.adj_matrix[u][v] = true;            self.adj_matrix[v][u] = true; // 无向图        }    }    fn has_edge(&self, u: usize, v: usize) -> bool {        self.adj_matrix[u][v]    }}  

Rust图表示方法二：邻接表（Adjacency List）

邻接表使用数组（或哈希表）存储每个节点的邻居列表。这是更常用的方法，尤其适用于稀疏图（边远少于节点平方）。

优点：节省空间，空间复杂度为 O(V + E)，其中 E 是边数。
缺点：查询两个节点是否相连需要遍历邻居列表，时间复杂度为 O(degree)。

// 使用 Vec<Vec<usize>> 表示无权无向图struct GraphList {    adj_list: Vec<Vec<usize>>,}impl GraphList {    fn new(n: usize) -> Self {        GraphList {            adj_list: vec![Vec::new(); n],        }    }    fn add_edge(&mut self, u: usize, v: usize) {        self.adj_list[u].push(v);        self.adj_list[v].push(u); // 无向图    }    fn neighbors(&self, u: usize) -> &[usize] {        &self.adj_list[u]    }}  

如何选择表示方法？

• 如果你的图是稠密图（边很多），且需要频繁查询两点是否相连，考虑使用邻接矩阵。
• 如果你的图是稀疏图（边较少），或者需要节省内存，推荐使用邻接表。

完整示例：构建并打印一个简单图

fn main() {    // 使用邻接表创建一个包含4个节点的图    let mut graph = GraphList::new(4);    graph.add_edge(0, 1);    graph.add_edge(0, 2);    graph.add_edge(1, 2);    graph.add_edge(2, 3);    println!("Node 0's neighbors: {:?}", graph.neighbors(0));    // 输出: [1, 2]}  

总结

通过本教程，你已经掌握了在Rust语言中实现图的两种基本方法：邻接矩阵和邻接表。无论你是学习Rust图算法实现，还是开发实际项目，这些基础都至关重要。

记住，选择合适的数据结构能极大提升程序效率。希望这篇Rust语言图教程能帮助你迈出图算法学习的第一步！

关键词：Rust图表示方法、Rust图数据结构、Rust图算法实现、Rust语言图教程