掌握图的遍历：Rust语言实现深度优先与广度优先搜索（Rust图遍历算法从入门到实战）

什么是图？

图由节点（顶点）和边组成。边可以是有向的（如 A → B）或无向的（A — B）。在 Rust 中，我们通常用邻接表（Adjacency List）来表示图，即每个节点对应一个列表，存储它能到达的所有邻居节点。

准备工作：定义图结构

首先，我们用 Rust 定义一个简单的有向图：

use std::collections::HashMap;#[derive(Debug, Clone)]pub struct Graph {    // 使用 HashMap 存储邻接表：节点 -> 邻居列表    adj_list: HashMap>,}impl Graph {    pub fn new() -> Self {        Graph {            adj_list: HashMap::new(),        }    }    // 添加节点（如果不存在）    pub fn add_node(&mut self, node: usize) {        self.adj_list.entry(node).or_insert_with(Vec::new);    }    // 添加有向边：from -> to    pub fn add_edge(&mut self, from: usize, to: usize) {        self.add_node(from);        self.add_node(to);        self.adj_list.get_mut(&from).unwrap().push(to);    }    // 获取某个节点的所有邻居    pub fn neighbors(&self, node: usize) -> Option<&Vec> {        self.adj_list.get(&node)    }    // 获取所有节点    pub fn nodes(&self) -> Vec {        self.adj_list.keys().cloned().collect()    }}

深度优先搜索（DFS）

深度优先搜索（DFS）是一种“一条路走到黑”的策略：从起点出发，不断深入访问未访问的邻居，直到无法继续，再回溯。

DFS 常用于检测环、拓扑排序、连通分量等。下面我们用递归方式实现 DFS：

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

广度优先搜索（BFS）

广度优先搜索（BFS）则像“水波扩散”：先访问起点的所有直接邻居，再访问邻居的邻居，依此类推。BFS 常用于求最短路径（在无权图中）。

BFS 通常使用队列（Queue）实现，在 Rust 中我们可以用 VecDeque：

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

完整示例：运行你的第一个图遍历

现在，让我们把所有代码组合起来，并测试一下：

fn main() {    let mut graph = Graph::new();    graph.add_edge(0, 1);    graph.add_edge(0, 2);    graph.add_edge(1, 3);    graph.add_edge(2, 3);    graph.add_edge(3, 4);    println!("DFS 遍历结果: {:?}", graph.dfs_recursive(0));    // 可能输出: [0, 1, 3, 4, 2]    println!("BFS 遍历结果: {:?}", graph.bfs(0));    // 可能输出: [0, 1, 2, 3, 4]}

注意：DFS 的结果可能因邻居顺序不同而变化，但 BFS 在无权图中总能保证按“层级”访问。

总结

通过本教程，你已经学会了如何在 Rust 中实现图的基本结构以及两种核心的广度优先搜索Rust和深度优先搜索Rust算法。这些是解决更复杂图问题（如最短路径、最小生成树）的基础。

建议你动手修改图的结构，尝试不同的起点，观察遍历顺序的变化。实践是掌握Rust算法教程的最佳方式！

如果你觉得这篇文章对你有帮助，欢迎分享给正在学习 Rust 或算法的朋友！