DFS/BFS 兩次找樹直徑與其證明

問題描述

給一棵 樹，每條邊都有權重，定義一條路徑的長度為該路徑上每條邊的權重和。

樹上的任何最長長度的簡單路徑都是此樹的直徑。

現在請你找到此樹上的任意一條直徑。

演算法

任選一點(令其為

$x$)出發，做一次 DFS 或 BFS 找到樹上離

$x$ 最遠的點

$y$，可證明點

$y$ 一定是某條直徑到其中一個端點，所以再從點

$y$ 出發做一次 DFS/BFS 找到離點

$y$ 最遠的點

$z$，那麼點

$y$ 和點

$z$ 形成的路徑就是直徑。

參考程式碼

可測試題目：TIOJ1213. 樹論 之 最遠距點對

1. DFS 的寫法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int SIZE = 1 << 20;
struct Data{
    int y;
    long long d;
    bool operator<(const Data& b) const {
        return d < b.d;
    }
};
vector<Data> e[SIZE];
int an[SIZE];
// 呼叫 dfs(x, lt, d) 代表從起點 DFS 後，目前走到點 x，上一個走的點是 lt，且已走過的邊數為 d
// 最終會回傳的 Data 為 {最遠的點的編號, 離起點最遠的點的距離}
Data dfs(int x, int lt, long long dis) {
    Data result = {x, dis};
    for(auto node: e[x]) {
        if(node.y == lt) continue;
        result = max(result, dfs(node.y, x, node.d + dis));
    }
    return result;
}
int main() {
    int n;
    cin >> n;
    for(int i = 1; i < n; i++) {
        int x, y, v;
        cin >> x >> y >> v;
        e[x].push_back({y, v});
        e[y].push_back({x, v});
    }
    int y = dfs(1, 1, 0).y;
    cout << dfs(y, y, 0).d << '\n';
}

2. BFS 的寫法：

#include <bits/stdc++.h>
using namespace std;

/* ------------ 常數與型別 ------------ */
const int MAX_N = 100'001;
// n ≤ 100 000（CSES 的限制），多開 1 個位置方便 1‑based index
struct Edge {
    int to;
    int w;
}; // to：鄰點編號，w：邊權
struct Data {       // 用來回傳「最遠點」資訊
    int id;         // 點編號
    long long dist; // 與起點距離
};

vector<Edge> G[MAX_N];    // 無向樹的鄰接串列
long long distArr[MAX_N]; // BFS 途中儲存距離
int parentArr[MAX_N];     // BFS 時的父節點（避免回頭）
/* ----------------------------------- */

/* --------------------- 單源 BFS：回傳離 start 最遠的點 --------------------
 * 由於樹中任兩節點之間的路徑唯一，只要「走到鄰點時把邊權加進去」，
 * 就能正確算出距離；整體複雜度 O(n)。
 */
Data bfs(int start, int n) {
    queue<int> que;
    /* 初始化起點 */
    fill(distArr + 1, distArr + n + 1, -1); // -1 代表尚未造訪
    que.push(start);
    distArr[start] = 0;
    parentArr[start] = 0;

    Data farthest{start, 0};

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (const auto &e : G[u]) {
            int v = e.to;
            if (v == parentArr[u]) continue; // 不回頭
            parentArr[v] = u;
            distArr[v] = distArr[u] + e.w;
            que.push(v);

            /* 即時更新目前最遠點 */
            if (distArr[v] > farthest.dist)
                farthest = {v, distArr[v]};
        }
    }
    return farthest;
}

/* ----------------------------- 主程式 ----------------------------- */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    // 讀取多組測資；當 n 為 0 時代表輸入結束
    while (cin >> n && n) {
        for (int i = 1; i <= n; i++) G[i].clear(); // 每組測資都必須重新初始化
        for (int i = 1; i < n; ++i) {
            int a, b, w;
            cin >> a >> b >> w;
            G[a].push_back({b, w});
            G[b].push_back({a, w});
        }

        /* 第一次 BFS：任取 1 為根，找出最遠點 u */
        int u = bfs(1, n).id;
        /* 第二次 BFS：由 u 出發，最遠距離即為樹的直徑 */
        long long diameter = bfs(u, n).dist;

        cout << diameter << '\n';
    }
    return 0;
}

證明

定義

$P(x,y)$ 代表以點

$x$ 和點

$y$ 為端點的簡單路徑，

$dis(x,y)$ 為

$P(x,y)$ 的長度。

我們只需證明，對於任一個點

$x$ 當作此樹的樹根，那麼距離點

$x$ 最遠的任一個葉子一定是某條直徑的端點即可。

使用反證法，令其中一個距離

$x$ 最遠的葉子為

$y$，假設

$y$ 並非任何一條直徑的端點。並假設

$P(u,v)$ 是某條直徑的兩個端點，那麼有以下兩種情況：

1. $P(u,v)$ 和
   $P(x,y)$ 至少有一個交點：
   在此種情況時，令
   $c$ 是它們的交點中，離
   $x$ 最遠的點，
   $P(u,c)$ 和
   $P(v,c)$ 一定有其中一條是完全在點
   $c$ 的子樹裡，不妨假設是
   $P(v,c)$ 在點
   $c$ 的子樹裡，那麼
   $dis(v,c)\le dis(v,y)$ 必成立(因為
   $y$ 是距離
   $x$ 最遠的葉子)，也就是說，把
   $P(u,v)$ 中
   $P(c,v)$ 的部分取代為
   $P(c,y)$，所得到的
   $P(u,y)$ 必滿足
   $dis(u,y)\ge dis(u,v)$，所以
   $P(u,y)$ 也會是直徑，和假設矛盾。
2. $P(u,v)$ 和
   $P(x,y)$ 沒有交點：
   令
   $c$ 為
   $u$ 和
   $v$ 的 LCA，也就是
   $P(u,v)$ 中距離
   $x$ 最近的點，類似於上一種，
   $dis(c,y)\ge dis(c,v)$ 必成立，所以
   $dis(u,y)\ge dis(u,v)$，所以
   $P(u,y)$ 也會是直徑，和假設矛盾。

在由於在兩種情況都矛盾，所以

$y$ 必定是某條直徑的端點。

參考資料

SA 流 C++ 競程修煉心法