Rust 算法精讲：用 DFS 玩转图遍历，从起点“一走到底”的秘密

图（Graph）是计算机科学中最重要的数据结构之一，而遍历图的两种核心算法——深度优先搜索（DFS）和广度优先搜索（BFS）——是所有程序员的必备技能。深度优先搜索 的策略是 “一走到底，再行回溯”，这种递归的特性使其在许多场景（如拓扑排序、连通性检查）中表现出色。

本文将以 Rust 语言的严谨性为基础，展示如何使用邻接表 (Vec<Vec<usize>>) 高效地存储图结构，并通过 递归函数 (dfs_util) 和 HashSet 实现一个稳健的 DFS 遍历。我们将重点解析 HashSet 如何保证算法在有环图结构中不会陷入无限循环。

实操

实现一个用于图（Graph） 结构的 深度优先搜索（DFS） 遍历算法。

DFS 的核心思想是 “一走到底”，即从起点出发，尽可能沿着一条路径深入，直到无路可走时才回溯。

/*
    dfs
    a basic DFS traversal
*/

use std::collections::HashSet;

struct Graph {
    adj: Vec<Vec<usize>>,
}

impl Graph {
    fn new(n: usize) -> Self {
        Graph {
            adj: vec![vec![]; n],
        }
    }

    fn add_edge(&mut self, src: usize, dest: usize) {
        self.adj[src].push(dest);
        self.adj[dest].push(src);
    }

    fn dfs_util(&self, v: usize, visited: &mut HashSet<usize>, visit_order: &mut Vec<usize>) {
        // 1. Mark the current node as visited and record it.
        visited.insert(v);
        visit_order.push(v);

        // 2. Recur for all adjacent vertices (depth-first)
        for &neighbor in &self.adj[v] {
            if !visited.contains(&neighbor) {
                // Dive deep into the unvisited neighbor
                self.dfs_util(neighbor, visited, visit_order);
            }
        }
    }

    // Perform a depth-first search on the graph, return the order of visited nodes
    fn dfs(&self, start: usize) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut visit_order = Vec::new();
        self.dfs_util(start, &mut visited, &mut visit_order);
        visit_order
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dfs_simple() {
        let mut graph = Graph::new(3);
        graph.add_edge(0, 1);
        graph.add_edge(1, 2);

        let visit_order = graph.dfs(0);
        assert_eq!(visit_order, vec![0, 1, 2]);
    }

    #[test]
    fn test_dfs_with_cycle() {
        let mut graph = Graph::new(4);
        graph.add_edge(0, 1);
        graph.add_edge(0, 2);
        graph.add_edge(1, 2);
        graph.add_edge(2, 3);
        graph.add_edge(3, 3);

        let visit_order = graph.dfs(0);
        assert_eq!(visit_order, vec![0, 1, 2, 3]);
    }

    #[test]
    fn test_dfs_disconnected_graph() {
        let mut graph = Graph::new(5);
        graph.add_edge(0, 1);
        graph.add_edge(0, 2);
        graph.add_edge(3, 4);

        let visit_order = graph.dfs(0);
        assert_eq!(visit_order, vec![0, 1, 2]);
        let visit_order_disconnected = graph.dfs(3);
        assert_eq!(visit_order_disconnected, vec![3, 4]);
    }
}

代码结构与 DFS 实现细节

该实现通过两个主要结构和三个核心方法完成了 DFS 遍历：

1. Graph 结构体

• adj: Vec<Vec<usize>> (邻接表): 这是图的主要数据结构。它是一个向量的向量，其中 adj[i] 存储了所有与节点 i 相连的邻居节点的索引（usize）。这种表示法适用于稀疏图，并且能够高效地查找节点的邻居。
• new(n: usize): 构造函数，创建一个包含 n 个节点的图，初始化邻接表，每个节点的邻居列表都是空的。
• add_edge(src: usize, dest: usize): 添加一条边。由于这段代码构建的是无向图，所以它会同时在两个节点的邻接表中添加连接：src 连接到 dest，同时 dest 连接到 src。

2. DFS 核心逻辑

DFS 遍历主要由两个相互调用的方法完成：

A. dfs(&self, start: usize) -> Vec<usize> (公有入口)

• 这是用户调用的公共方法，负责初始化 DFS 过程。
• 它创建了两个可变状态容器，作为 DFS 遍历过程中的“记忆”：
  • visited: HashSet<usize>: 使用 HashSet 来存储已经被访问过的节点。HashSet 提供了O(1) 的平均时间复杂度来检查节点是否已访问，这对于防止重复遍历和无限循环至关重要。
  • visit_order: Vec<usize>: 存储 DFS 遍历过程中节点被访问的顺序。
• 最后，它调用私有递归函数 dfs_util 开始遍历，并返回最终的遍历顺序。

B. dfs_util(&self, v: usize, visited: &mut HashSet<usize>, visit_order: &mut Vec<usize>) (私有递归)

这是执行深度优先搜索的递归函数：

1. 访问并标记： 函数首先将当前节点 v 标记为已访问 (visited.insert(v))，并将其添加到遍历顺序列表 (visit_order.push(v))。
2. 深度探索： 接着，它遍历当前节点 v 的所有邻居节点（&self.adj[v]）。
3. 递归下潜： 对于每一个未被访问的邻居节点 (if !visited.contains(&neighbor))，函数会递归调用自身 (self.dfs_util(...))，从而沿着这条路径不断深入，直到达到图的末端或遇到已访问的节点，完美体现了 DFS “深度优先”的特性。

测试用例分析

代码附带的测试用例验证了 DFS 在不同图结构下的正确性：

• test_dfs_simple: 验证了简单线性图的遍历，预期结果是 [0, 1, 2]，体现了遍历的顺序性。
• test_dfs_with_cycle: 验证了 DFS 在存在环的图中的行为。通过 visited 集合，DFS 能够检测并跳过已访问的节点（例如节点 2 的邻居 1 和 0），从而避免无限循环，并输出正确的遍历路径 [0, 1, 2, 3]。
• test_dfs_disconnected_graph: 验证了 DFS 对不连通图的处理。从节点 0 开始只能访问 [0, 1, 2] 所在的子图；从节点 3 开始则只能访问 [3, 4] 所在的子图，证明了 DFS 只能遍历与起始节点连通的那些节点。

总而言之，这段代码是一个清晰、高效的 Rust 实现，使用邻接表存储图，并利用递归和 HashSet 实现了标准的深度优先搜索算法。

总结

通过本次 DFS 算法的实践，我们成功地掌握了使用 Rust 实现图遍历的核心模式。

关键的学习点在于 dfs_util 递归函数的优雅实现：它通过引用传递可变状态（visited 和 visit_order），确保了遍历过程中的数据安全和高效性。HashSet 作为 “记忆”，其 O(1) 的平均查找时间复杂度是保证 DFS 性能的关键，它让算法能够快速判断节点是否已访问，从而避免了环路导致的程序崩溃。

这种基于邻接表、递归和访问标记的 DFS 模板是解决大多数图问题（如查找路径、判断连通性）的基石，证明了 Rust 在编写高性能、复杂算法时的强大能力。

参考

• https://www.rust-lang.org/zh-CN
• https://course.rs/about-book.html
• https://probe.rs/docs/tools/debugger/#installation
• https://rustwiki.org/
• https://doc.rust-lang.org/stable/rust-by-example/index.html