图遍历：BFS 与 DFS

唯一的新麻烦：环

走一棵树是无忧无虑的，因为树没有环——递归会自然地在叶子处触底。图不一样：顺着边走，你可能转一圈又回到出发点。如果你探索 A→B→C→A→B→C……你会永远转下去。所以每一次图遍历都带着一份树从不需要的额外记账：一个访问集合——记下你已经见过哪些顶点，从而每个最多只访问一次。

有了这一道保险，两种遍历就共用同一副骨架：从某处开始，把它标为已访问，不断扩展到*未访问*的邻居，直到用完为止。两个有名的算法之间唯一的区别，是它们取下一个待扩展顶点的顺序——而正是这一个选择，赋予了它们截然不同的性格。

广度优先搜索：扩张的环

[[breadth-first-search|广度优先搜索]]（BFS）的探索像池塘里的涟漪：先是起点，然后是它*所有*的直接邻居，再然后是离这些再走一步的一切，如此类推——一层一层来。产生这个顺序的工具，就是你在线性结构那一级学的[[queue|队列]]：先进先出。你把起点入队，然后反复出队一个顶点、把它未访问的邻居入队。因为队列按顶点被发现的顺序把它们交还回来，所以更近的顶点总是先于更远的出来。

  start=0     BFS visit order, level by level:
   (0)        level 0: 0
   / \        level 1: 1, 2     (neighbors of 0)
 (1) (2)      level 2: 3, 4     (one more step out)
  |    |
 (3)  (4)     0 is found at distance 0, 3 at distance 2.

BFS 以距起点等距的环向外铺开：第 0 层，再第 1 层，再第 2 层。

#include <queue>
#include <vector>
void bfs(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<bool> visited(adj.size(), false);
    std::queue<int> q;
    visited[start] = true;          // mark on discovery, not on visit
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        std::cout << u << ' ';      // process u
        for (int v : adj[u])        // each unvisited neighbor
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
    }
}

用 std::queue 和一个 visited 向量实现的 BFS。每个顶点入队一次；每条边检查一次。

那种一圈一圈的顺序，正是 BFS 的超能力：在无权图里，BFS 第一次到达某个顶点时，是用了*尽可能少的边*到达的。所以 BFS 能找到从起点到其他每个顶点的最短路径（以跳数计）——记下每个顶点是被谁发现的，你就能重建路线。在树上运行时，它恰好就是*层序*遍历。

深度优先搜索：沿一条路走到底

[[depth-first-search|深度优先搜索]]（DFS）的性情正相反。它不均匀铺开，而是认准一条路，能走多深就走多深，只有撞到死胡同才回退。这就像你扶着一面墙探索迷宫的走法。它天然的引擎是[[dsa-recursion|递归]]的调用栈（后进先出）——你递归进入一个邻居，运行时会记住该回到哪里。（你也可以用一个显式的 `std::stack` 来做，那是它迭代版的孪生兄弟。）

void dfs(const std::vector<std::vector<int>>& adj,
         int u, std::vector<bool>& visited) {
    visited[u] = true;
    std::cout << u << ' ';          // process u
    for (int v : adj[u])            // dive into the first
        if (!visited[v])            // unvisited neighbor,
            dfs(adj, v, visited);   // all the way down, then backtrack
}
// call: std::vector<bool> visited(adj.size(), false);
//       dfs(adj, 0, visited);

用递归实现的 DFS——调用栈替你记账。visited 向量依然防着环。

BFS 和 DFS 的代价相同。每个顶点处理一次，每条边查看一次，所以总工作量是 O(V + E)——V 数顶点，E 数边。正是这个线性代价，让遍历成为那些更花哨的图算法赖以建立的、既便宜又可靠的地基。

这解锁了什么

这两种遍历是门，不是终点。一旦你能系统地访问一张图，一整本问题目录就打开了——下面预览一下近在眼前的东西。

连通性与环检测 — 跑一次遍历，看你能到达什么，或者是否绕回过。
[[shortest-path|最短路径]] — 无权图用 BFS 就解决了；当边带权时，你会用上 Dijkstra 算法，它是建立在同样“向外扩张”想法之上的带权表亲。
[[topological-sort|拓扑排序]] — 对一张有向无环图（比如任务依赖），DFS 能给出一个合法的做事顺序，使任何事都不会排在它的前置条件之前。