圖遍歷：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 能給出一個合法的做事順序，使任何事都不會排在它的前置條件之前。