图的遍历之旅（用Rust轻松掌握DFS与BFS）

什么是图？

图由节点（也叫顶点）和边组成。例如，你可以把城市看作节点，高速公路看作边。图可以是有向的（边有方向）或无向的（边无方向）。

准备工作：定义图结构

在 Rust 中，我们可以用 Vec<Vec<usize>> 来表示一个邻接表形式的图。每个索引代表一个节点，其对应的 Vec 存储它能直接到达的邻居节点。

// 定义图：使用邻接表let graph = vec![    vec![1, 2],    // 节点0连接到1和2    vec![3],       // 节点1连接到3    vec![3],       // 节点2连接到3    vec![],        // 节点3没有出边];

深度优先搜索（DFS）

深度优先搜索（DFS）就像走迷宫时“一条路走到黑”，直到无法前进再回退。它通常用递归或栈实现。

在 Rust 中，我们可以用递归方式实现 DFS：

fn dfs(graph: &Vec<Vec<usize>>, node: usize, visited: &mut Vec<bool>) {    if visited[node] {        return;    }    println!("访问节点: {}", node);    visited[node] = true;    for &neighbor in &graph[node] {        dfs(graph, neighbor, visited);    }}// 使用示例fn main() {    let graph = vec![vec![1, 2], vec![3], vec![3], vec![]];    let mut visited = vec![false; graph.len()];    dfs(&graph, 0, &mut visited);}

这段代码会输出：访问节点: 0 → 1 → 3 → 2（具体顺序可能因实现细节略有不同）。

广度优先搜索（BFS）

广度优先搜索（BFS）则像水波一样一层层扩散，先访问离起点最近的所有节点。它通常用队列实现。

Rust 标准库中的 std::collections::VecDeque 非常适合做队列：

use std::collections::VecDeque;fn bfs(graph: &Vec<Vec<usize>>, start: usize) {    let mut visited = vec![false; graph.len()];    let mut queue = VecDeque::new();        queue.push_back(start);    visited[start] = true;    while let Some(node) = queue.pop_front() {        println!("访问节点: {}", node);        for &neighbor in &graph[node] {            if !visited[neighbor] {                visited[neighbor] = true;                queue.push_back(neighbor);            }        }    }}// 使用示例fn main() {    let graph = vec![vec![1, 2], vec![3], vec![3], vec![]];    bfs(&graph, 0);}

这段代码会输出：访问节点: 0 → 1 → 2 → 3，体现了“层级遍历”的特点。

对比与应用场景

• DFS 适合用于检测环、拓扑排序、解决迷宫问题等。
• BFS 适合用于求最短路径（在无权图中）、层级遍历、社交网络中的“六度空间”等问题。

无论你是学习 Rust图遍历，还是想掌握 深度优先搜索 与 广度优先搜索 的核心思想，本文都为你打下了坚实基础。配合动手实践，你很快就能在项目中灵活运用这些算法！

结语

Rust 的内存安全和零成本抽象特性，使其成为实现高效图算法的理想选择。希望这篇 Rust算法教程 能帮助你迈出图论学习的第一步。继续编码，继续探索！