Paxon Qiao's Tech Blog

用 Rust 优雅实现图搜索核心算法：广度优先搜索 (BFS) 实战

· 8min · Paxon Qiao
Table of Contents

用 Rust 优雅实现图搜索核心算法：广度优先搜索 (BFS) 实战

在计算机科学中，图（Graph）是表示对象之间关系的核心数据结构，而图搜索算法则是解决迷宫、网络路由、社交关系分析等问题的关键。其中，**广度优先搜索（Breadth-First Search, BFS）因其能保证发现最短路径（针对无权图）**而被广泛使用。

本次我们将聚焦于 Rust 语言，展示如何用它强大的结构体和高效的集合库来实现这一经典算法。Rust 以其内存安全和并发性能著称，天然适合处理复杂的图结构。我们将详细解析代码中的 Graph 结构体、邻接表的表示方式，以及如何利用 VecDeque 来完美模拟 BFS 所需的先进先出（FIFO）队列逻辑。通过这段代码，您将体会到 Rust 在实现底层算法时的优雅与严谨。

广度优先搜索 (BFS) 是图遍历算法的基石，常用于寻路和最短路径计算。本文通过一段精简的 Rust 代码，实操演示了如何利用 VecDeque 集合库和邻接表高效实现 BFS 算法。Rust 的所有权和类型系统确保了图结构的内存安全，而清晰的队列逻辑则保证了节点能按层次顺序被访问。

实操

如何用 Rust 的结构体和集合库实现经典的 BFS 算法。

/*
    bfs
    a basic BFS algorithm
*/

use std::collections::VecDeque;

// Define a graph
struct Graph {
    adj: Vec<Vec<usize>>,
}

impl Graph {
    // Create a new graph with n vertices
    fn new(n: usize) -> Self {
        Graph {
            adj: vec![vec![]; n],
        }
    }

    // Add an edge to the graph
    fn add_edge(&mut self, src: usize, dest: usize) {
        self.adj[src].push(dest);
        self.adj[dest].push(src);
    }

    // Perform a breadth-first search on the graph, return the order of visited nodes
    fn bfs_with_return(&self, start: usize) -> Vec<usize> {
        let n = self.adj.len();
        if n == 0 {
            return vec![];
        }

        // 1. Initialization
        // `visited` array to keep track of discovered nodes
        let mut visited = vec![false; n];

        // `queue` for managing the nodes to explore (FIFO order)
        let mut queue: VecDeque<usize> = VecDeque::new();

        // `visit_order` to store the final result sequence
        let mut visit_order = vec![];

        // 2. Start the BFS
        // Mark the start node as visited and enqueue it
        visited[start] = true;
        queue.push_back(start);

        // 3. Main loop: Continue while there are nodes in the queue
        while let Some(u) = queue.pop_front() {
            // Dequeue the node and record it in the final order
            visit_order.push(u);

            // Explore all neighbors (v) of the current node (u)
            for &v in &self.adj[u] {
                // If the neighbor 'v' has not been visited
                if !visited[v] {
                    // Mark it as visited and enqueue it for later exploration
                    visited[v] = true;
                    queue.push_back(v);
                }
            }
        }
        visit_order
    }
}

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

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

        let visited_order = graph.bfs_with_return(0);
        assert_eq!(visited_order, vec![0, 1, 4, 2, 3]);
    }

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

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

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

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

    #[test]
    fn test_bfs_single_node() {
        let mut graph = Graph::new(1);

        let visited_order = graph.bfs_with_return(0);
        assert_eq!(visited_order, vec![0]);
    }
}

Rust 实现广度优先搜索 (BFS) 算法解析

这段 Rust 代码提供了一个基础的图结构 Graph，并实现了一个核心算法：bfs_with_return，即广度优先搜索。BFS 是一种用于遍历或搜索树或图的算法，其特点是先访问离起始点近的节点，再访问离起始点远的节点，像水波纹一样一层一层向外扩展。

1. 图结构 (struct Graph)

核心结构

图被定义为一个结构体 Graph，它使用邻接表（Adjacency List）来存储图的连接信息：

struct Graph {
    adj: Vec<Vec<usize>>, // 邻接表
}
  • adj: Vec<Vec<usize>>: 这是一个嵌套的向量（Vector）。外层 Vec 的每个索引代表图中的一个节点（顶点），内层 Vec<usize> 存储的是该节点所有直接相邻的节点的索引。
    • 例如，adj[0] 存储的就是节点 0 的所有邻居。

关键方法

  1. fn new(n: usize) -> Self: 构造函数，用于创建一个具有 n 个节点的图。它初始化了一个包含 n 个空向量的邻接表。
  2. fn add_edge(&mut self, src: usize, dest: usize): 用于在图中的两个节点（src 和 dest）之间添加一条边。
    • 注意，代码中同时执行了 self.adj[src].push(dest) 和 self.adj[dest].push(src)，这意味着这是一个无向图的实现（边是双向的）。

2. 广度优先搜索实现 (fn bfs_with_return)

bfs_with_return 是实现 BFS 算法的核心函数，它接收一个起始节点 start，并返回一个包含节点访问顺序的向量。

核心思想：使用队列（Queue）

BFS 算法的灵魂在于使用一个**队列（Queue）**来管理待访问的节点。队列遵循 FIFO (先进先出) 原则，这保证了算法会先探索所有当前节点的邻居（即同层节点），然后再继续深入下一层。

实现步骤详解

  1. 初始化 (Initialization)
    • let mut visited = vec![false; n];: 创建一个布尔型向量，大小与节点数相同。它用于标记节点是否已被访问过，避免重复访问和陷入循环，这是图遍历算法的通用关键机制。
    • let mut queue: VecDeque<usize> = VecDeque::new();: 使用 std::collections::VecDeque 作为队列。在 Rust 中，VecDeque 提供了高效的队列操作 (push_back 和 pop_front)。
    • let mut visit_order = vec![];: 用于记录算法最终遍历到的节点顺序。
  2. 起始处理 (Start the BFS)
    • visited[start] = true;: 将起始节点标记为已访问。
    • queue.push_back(start);: 将起始节点加入队列的末尾，等待处理。
  3. 主循环 (Main Loop)
    • while let Some(u) = queue.pop_front() { ... }: 循环将持续进行，直到队列为空（即所有可达节点都已访问完毕）。每次循环都从队列的头部取出（pop_front）一个节点 u 进行处理。
    • visit_order.push(u);: 将当前被取出的节点 u 记录到最终的访问顺序中。
  4. 探索邻居 (Explore Neighbors)
    • for &v in &self.adj[u] { ... }: 遍历节点 u 的所有邻居节点 v。
    • if !visited[v]: 检查邻居 v 是否已经被访问过。
    • visited[v] = true;: 如果 v 是新节点，立即将其标记为已访问。
    • queue.push_back(v);: 将新发现的节点 v 加入队列的末尾。这确保了在处理完当前节点的所有其他邻居之后，v 才会轮到被处理，从而实现广度优先。
  5. 返回结果
    • 循环结束后，函数返回包含所有已访问节点顺序的 visit_order 向量。

总结

通过这段简洁而功能完备的 Rust 代码，我们不仅成功实现了广度优先搜索（BFS）算法，更重要的是，我们体验了 Rust 在算法设计中的几大优势。

首先，Graph 结构体的模块化设计使得图的创建和边的添加清晰易懂。其次，利用 std::collections::VecDeque 实现了高效的队列操作，这是 BFS 算法性能的关键。最后，使用 visited 布尔数组来精确追踪节点状态，体现了 Rust 代码的安全性和严谨性，有效避免了循环和重复计算。

掌握 BFS 是进阶图算法的基础。未来，您可以基于这段代码进一步尝试实现深度优先搜索（DFS），或者将其扩展到加权图（Weighted Graphs），为寻找带权最短路径（如 Dijkstra 算法）奠定坚实的基础。Rust 的性能和安全性，将为您的算法实践提供强大的保障。

参考