掌握Rust图算法（从零开始构建图数据结构与实现遍历算法）

在 Rust 中表示图

最常用的图表示方法有两种：

• 邻接矩阵（Adjacency Matrix）：用二维数组表示节点间是否相连。
• 邻接表（Adjacency List）：用哈希表或向量存储每个节点的邻居列表。

对于稀疏图（边远少于节点数平方），邻接表更节省空间。我们选择邻接表作为实现方式。

定义图结构

首先，我们使用 HashMap 来存储图：

use std::collections::{HashMap, HashSet};#[derive(Debug, Clone)]pub struct Graph {    // 使用 HashMap 存储每个节点及其邻居集合    adj_list: HashMap<String, HashSet<String>>,}impl Graph {    pub fn new() -> Self {        Graph {            adj_list: HashMap::new(),        }    }    // 添加节点    pub fn add_vertex(&mut self, vertex: String) {        self.adj_list.entry(vertex).or_insert(HashSet::new());    }    // 添加无向边    pub fn add_edge(&mut self, v1: String, v2: String) {        self.add_vertex(v1.clone());        self.add_vertex(v2.clone());        self.adj_list.get_mut(&v1).unwrap().insert(v2.clone());        self.adj_list.get_mut(&v2).unwrap().insert(v1);    }    // 获取邻居    pub fn neighbors(&self, vertex: &str) -> Option<&HashSet<String>> {        self.adj_list.get(vertex)    }}  

实现图遍历算法

图遍历是图算法的基础，用于访问图中所有可达节点。我们重点介绍两种经典方法：

1. 深度优先搜索（DFS）

DFS 使用栈（递归或显式栈）深入探索一条路径，直到无法继续，再回溯。

use std::collections::HashSet;impl Graph {    pub fn dfs(&self, start: &str) -> Vec<String> {        let mut visited = HashSet::new();        let mut result = Vec::new();        self.dfs_helper(start, &mut visited, &mut result);        result    }    fn dfs_helper(        &self,        vertex: &str,        visited: &mut HashSet<String>,        result: &mut Vec<String>,    ) {        if visited.contains(vertex) {            return;        }        visited.insert(vertex.to_string());        result.push(vertex.to_string());        if let Some(neighbors) = self.neighbors(vertex) {            for neighbor in neighbors {                self.dfs_helper(neighbor, visited, result);            }        }    }}  

2. 广度优先搜索（BFS）

BFS 使用队列逐层访问节点，适合寻找最短路径（在无权图中）。

use std::collections::{HashSet, VecDeque};impl Graph {    pub fn bfs(&self, start: &str) -> Vec<String> {        let mut visited = HashSet::new();        let mut queue = VecDeque::new();        let mut result = Vec::new();        queue.push_back(start.to_string());        visited.insert(start.to_string());        while let Some(vertex) = queue.pop_front() {            result.push(vertex.clone());            if let Some(neighbors) = self.neighbors(&vertex) {                for neighbor in neighbors {                    if !visited.contains(neighbor) {                        visited.insert(neighbor.clone());                        queue.push_back(neighbor.clone());                    }                }            }        }        result    }}  

完整示例：构建并遍历一个简单图

让我们创建一个包含 4 个节点的小图，并分别运行 DFS 和 BFS：

fn main() {    let mut graph = Graph::new();    graph.add_edge("A".to_string(), "B".to_string());    graph.add_edge("A".to_string(), "C".to_string());    graph.add_edge("B".to_string(), "D".to_string());    graph.add_edge("C".to_string(), "D".to_string());    println!("DFS: {:?}", graph.dfs("A"));    // 可能输出：DFS: ["A", "B", "D", "C"]    println!("BFS: {:?}", graph.bfs("A"));    // 可能输出：BFS: ["A", "B", "C", "D"]}  

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

Rust 的所有权系统和零成本抽象使其在处理复杂数据结构（如图）时既安全又高效。没有垃圾回收机制意味着更低的延迟，非常适合需要高性能的图遍历算法场景。

总结

通过本教程，你已经学会了：

• 如何在 Rust 中定义图数据结构；
• 如何实现 DFS 和 BFS 两种核心Rust编程教程中必学的遍历算法；
• 理解了图在实际问题中的应用价值。

下一步，你可以尝试实现更复杂的算法，如 Dijkstra 最短路径、拓扑排序或连通分量检测。Rust 的强大类型系统和工具链（如 Cargo）将助你一臂之力！

希望这篇关于Rust图算法的入门指南对你有所帮助。动手实践是掌握知识的最佳方式，快去写代码吧！