Rust语言实现深度优先搜索（DFS）详解：从零开始掌握图遍历算法

什么是深度优先搜索？

深度优先搜索（DFS）的基本思想是：从起始节点出发，沿着一条路径尽可能深入地访问节点，直到无法继续为止，然后回溯并尝试其他路径。这种“深入到底再回头”的策略非常适合用递归来实现。

为什么选择 Rust 实现 DFS？

Rust 是一门内存安全、高性能的系统编程语言。它通过所有权（ownership）和借用（borrowing）机制，在编译期就避免了空指针、数据竞争等常见错误。使用 Rust 编写DFS算法不仅能提升代码安全性，还能获得接近 C/C++ 的执行效率。

准备工作：定义图结构

在 Rust 中，我们可以用邻接表（Adjacency List）来表示图。邻接表是一个数组（或向量），其中每个元素是一个列表，存储与该节点相邻的所有节点。

// 定义图结构struct Graph {    adj_list: Vec<Vec<usize>>,}impl Graph {    // 创建新图    fn new(n: usize) -> Self {        Graph {            adj_list: vec![vec![]; n],        }    }    // 添加边（无向图）    fn add_edge(&mut self, u: usize, v: usize) {        self.adj_list[u].push(v);        self.adj_list[v].push(u);    }}

实现深度优先搜索（递归版）

接下来，我们编写一个递归函数来执行 DFS。我们需要一个布尔数组来记录哪些节点已经被访问过，防止重复访问。

// 深度优先搜索函数fn dfs_recursive(graph: &Graph, node: usize, visited: &mut Vec<bool>) {    // 标记当前节点为已访问    visited[node] = true;    println!("访问节点: {}", node);    // 遍历所有相邻节点    for &neighbor in &graph.adj_list[node] {        if !visited[neighbor] {            dfs_recursive(graph, neighbor, visited);        }    }}

完整示例：构建图并运行 DFS

下面是一个完整的可运行示例：

fn main() {    // 创建一个包含5个节点的图    let mut graph = Graph::new(5);    // 添加边    graph.add_edge(0, 1);    graph.add_edge(0, 2);    graph.add_edge(1, 3);    graph.add_edge(1, 4);    // 初始化访问数组    let mut visited = vec![false; 5];    // 从节点0开始深度优先搜索    println!("开始深度优先搜索...");    dfs_recursive(&graph, 0, &mut visited);}

运行这段代码，你将看到如下输出：

开始深度优先搜索...访问节点: 0访问节点: 1访问节点: 3访问节点: 4访问节点: 2

进阶：非递归 DFS（使用栈）

虽然递归实现简洁，但在处理非常深的图时可能导致栈溢出。我们可以使用显式栈（Stack）来实现非递归版本：

use std::collections::VecDeque;// 非递归 DFSfn dfs_iterative(graph: &Graph, start: usize) {    let mut visited = vec![false; graph.adj_list.len()];    let mut stack = VecDeque::new();    stack.push_back(start);    while let Some(node) = stack.pop_back() {        if visited[node] {            continue;        }        visited[node] = true;        println!("访问节点: {}", node);        // 将邻居加入栈（注意顺序）        for &neighbor in &graph.adj_list[node] {            if !visited[neighbor] {                stack.push_back(neighbor);            }        }    }}

总结

通过本教程，你已经学会了如何在 Rust 中实现深度优先搜索（DFS）算法，包括递归和非递归两种方式。DFS 是许多高级算法（如拓扑排序、连通分量检测、迷宫求解等）的基础。掌握它，你就迈出了成为高效Rust图遍历开发者的重要一步！

记住，实践是最好的老师。尝试修改图的结构、添加更多节点，或者将 DFS 应用于实际问题（比如判断图是否连通），来巩固你的理解。

希望这篇关于Rust递归实现 DFS 的教程对你有帮助！如果你有任何问题，欢迎在评论区留言交流。