樹中的最長路徑：直徑問題解析與雙重搜尋法

問題背景

小Ho擁有一棵由N個節點（標號1至N）和N-1條邊構成的樹形玩具。小Hi出了一道題目：找出樹中距離最遠的兩個節點之間的距離，距離定義為路徑上邊的數量。這就是經典的「樹的直徑」問題。

核心洞見：任意節點出發的最遠點必是直徑端點

設樹的直徑端點為v1和v2。有一個關鍵性質：從任意節點u出發，走到的最遠節點一定是v1或v2其中之一。因此，我們可以通過兩次圖搜尋（BFS或DFS）來求解：

1. 從任意節點（如1）出發，找到距離最遠的節點v1。
2. 從v1出發，找到距離最遠的節點v2，兩者之間的距離即為樹的直徑長度。

算法實現要點

• 圖的儲存：使用鄰接表（vector），注意開雙倍空間存儲無向邊。
• 搜尋過程：維護訪問標記陣列，記錄當前路徑長度，更新最大長度與對應端點。
• 複雜度：時間O(N)，空間O(N)，滿足N≤10^5的限制。

參考代碼框架 (C++)

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 100005;
vector<int> tree[MAXN];
bool vis[MAXN];
int farthest_node, max_len;

void dfs(int u, int len) {
    vis[u] = true;
    if (len > max_len) {
        max_len = len;
        farthest_node = u;
    }
    for (int v : tree[u]) {
        if (!vis[v]) dfs(v, len + 1);
    }
}

int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; ++i) tree[i].clear();
        for (int i = 1; i < N; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        memset(vis, 0, sizeof(vis));
        max_len = -1;
        dfs(1, 0);           // 第一次搜尋找到 v1
        int v1 = farthest_node;

        memset(vis, 0, sizeof(vis));
        max_len = -1;
        dfs(v1, 0);          // 第二次搜尋找到 v2 及直徑長度
        printf("%d\n", max_len);
    }
    return 0;
}

總結

「兩次DFS/BFS」法利用樹的拓撲性質，以線性時間優雅地解決了樹的直徑問題，是圖論基礎中的經典技巧。