Rust 算法精讲：用 DFS 玩转图遍历，从起点“一走到底”的秘密
Table of Contents
Rust 算法精讲：用 DFS 玩转图遍历，从起点“一走到底”的秘密
图（Graph）是计算机科学中最重要的数据结构之一，而遍历图的两种核心算法——深度优先搜索（DFS）和广度优先搜索（BFS）——是所有程序员的必备技能。深度优先搜索的策略是**“一走到底，再行回溯”**，这种递归的特性使其在许多场景（如拓扑排序、连通性检查）中表现出色。
本文将以 Rust 语言的严谨性为基础，展示如何使用邻接表 (Vec<Vec<usize>>) 高效地存储图结构，并通过 递归函数 (dfs_util) 和 HashSet 实现一个稳健的 DFS 遍历。我们将重点解析 HashSet 如何保证算法在有环图结构中不会陷入无限循环。
Rust 深度优先搜索（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>) (私有递归)
这是执行深度优先搜索的递归函数：
- 访问并标记： 函数首先将当前节点
v标记为已访问 (visited.insert(v))，并将其添加到遍历顺序列表 (visit_order.push(v))。 - 深度探索： 接着，它遍历当前节点
v的所有邻居节点（&self.adj[v]）。 - 递归下潜： 对于每一个未被访问的邻居节点 (
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 在编写高性能、复杂算法时的强大能力。