樹上走訪

樹是沒有環的圖，所以走它只要記住「從哪來」。 · ⏱ 約 35 分鐘

你會學到三件事

1. 樹是一種特別的圖：n 個點、n−1 條邊、沒有環
2. DFS 走樹只要記 parent，不用 visited 陣列
3. 深度是一路傳下去的

開始之前

第 11 課的 BFS 需要一個 dist 陣列擋住走過的點。

樹上不用，因為沒有環：你只可能從來的那條邊走回去。

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、樹的三個等價說法

⚠️ 三個是等價的，證明其中一個就有另外兩個。 題目說「保證是一棵樹」時，這三件事你都可以用。

二、DFS 只要記 parent

樹上不會繞回去，所以記住「從哪裡來」就夠了：

1void dfs(int u, int parent) {2    vector<int> nb = g[u];3    for (int v : nb) {4        if (v == parent) continue;      // 🔴 唯一要擋的5        depth[v] = depth[u] + 1;6        dfs(v, u);                      // 我是 v 的 parent7    }8}

一般的圖要 visited 陣列，而樹上只要擋住「回頭那一步」。

因為沒有環，除了來的那條邊，其他邊都通向沒去過的地方。

⚠️ 呼叫時根的 parent 給 -1（一個不存在的點）：

1dfs(0, -1);

三、深度是傳下去的

深度不用另外算——往下走一層就加一：

1depth[v] = depth[u] + 1;

⚠️ 這一行要在 dfs(v, u) 之前：先設好，再往下走。

放在後面的話，子節點在計算時拿到的是舊值（多半是 0）。 症狀是所有深度都變成 0 或 1，而程式不會報錯。

    0        depth = 0
    |
    1        depth = 1
    |
    2        depth = 2

四、同一個形狀，換一個地方做事

樹上的 DFS 有兩個時機：

1void dfs(int u, int parent) {2    // ① 【進入】u 的時候——由上往下傳的東西（深度、從根到這裡的和）3    for (int v : g[u]) {4        if (v == parent) continue;5        dfs(v, u);6        // ② 【子樹處理完】——由下往上收的東西（子樹大小、子樹最大值）7    }8}

1size[u] = 1;2for (int v : g[u]) {3    if (v == parent) continue;4    dfs(v, u);5    size[u] += size[v];      // ← 在②，因為要等 v 算完6}

「往下傳」和「往上收」是樹上演算法的兩個方向， 而它們只差在你把那行程式寫在遞迴呼叫的前面還是後面。

五、⚠️ 遞迴深度

一條鏈狀的樹（每個點只有一個小孩），n = 10⁵ 的話遞迴會疊 10⁵ 層， 可能 stack overflow（第 5 課）。

競賽裡多半沒事，而真的爆了就要改成用 stack 的迴圈版本。

完成的樣子

1#include <iostream>2#include <vector>3using namespace std;4vector<vector<int>> g;5vector<int> depth(3, 0);6 7void dfs(int u, int parent) {8    vector<int> nb = g[u];9    for (int v : nb) {10        if (v == parent) continue;11        depth[v] = depth[u] + 1;12        dfs(v, u);13    }14}15 16int main() {17    vector<int> a;18    a.push_back(1);19    vector<int> b;20    b.push_back(0);21    b.push_back(2);22    vector<int> c;23    c.push_back(1);24    g.push_back(a);25    g.push_back(b);26    g.push_back(c);27    dfs(0, -1);28    cout << depth[2] << endl;29    return 0;30}

換你了

加一個 size 陣列，算出每個節點的子樹大小。

⚠️ 記得它要放在遞迴呼叫的後面，那是「往上收」。

到編輯器做這一題：練習：算出每個節點的子樹大小

做一個

一棵樹，邊是 0-1、0-2、1-3、3-4、2-5。以 0 為根，印出最深的節點和它的深度。

🔴 深度是一路傳下去的：dfs(v, u, d + 1)。 ⚠️ 而這一題不用 visited 陣列——記住 parent 就夠了，因為樹沒有環。

到編輯器做這一題：做一個：最深的那個節點

這一課你做了什麼

• 你知道樹是 n−1 條邊、沒有環的圖
• 你用 parent 取代了 visited 陣列
• 你分得出「往下傳」和「往上收」該寫在哪裡

如果卡住了