【定義】

給定一棵樹，樹中的每條邊都有一個(gè)權(quán)值。

• 樹中兩點(diǎn)的距離：連接兩點(diǎn)的路徑邊權(quán)之和
• 樹的直徑：樹中最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離
• 樹的最長(zhǎng)鏈：連接樹中最遠(yuǎn)的兩個(gè)結(jié)點(diǎn)的路徑

【實(shí)現(xiàn)】

樹的直徑通常有兩種求法，時(shí)間復(fù)雜度均為O(n)。

假設(shè)樹以 n 個(gè)點(diǎn) n-1 條邊的無向圖形式給出，存儲(chǔ)在鄰接表中。

1.兩次DFS求樹的直徑

通過兩次 dfs 可以求樹的直徑，且更容易計(jì)算出直徑上的具體結(jié)點(diǎn)

從任意結(jié)點(diǎn)出發(fā)，通過 dfs 對(duì)樹進(jìn)行一次遍歷，求出于出發(fā)點(diǎn)距離最遠(yuǎn)的結(jié)點(diǎn)，記為 st

從結(jié)點(diǎn) st 出發(fā)，通過 dfs 對(duì)樹再進(jìn)行一次遍歷，求出于 st 距離最遠(yuǎn)的結(jié)點(diǎn)，記為 ed

則：st 到 ed 的路徑就是樹的直徑

在第 2 步的遍歷中，可以記錄下來每個(gè)點(diǎn)第一次被訪問的前驅(qū)節(jié)點(diǎn)，最后從 q 遞歸到 p，即可得到直徑的具體方案

struct Edge {int to, val;int next;Edge(){}Edge(int to,int val,int next):to(to),val(val),next(next){} } edge[N]; int n; int head[N], tot; int dis[N], maxx, id; int st, ed, diameter;//起點(diǎn)、終點(diǎn)、直徑 int disSt[N], disEd[N];//起點(diǎn)、終點(diǎn)分別到每個(gè)點(diǎn)的距離 void addEdge(int from, int to, int val) {edge[++tot].to = to;edge[tot].val = val;edge[tot].next = head[from];head[from] = tot; } void dfs(int x, int father) {for (int i = head[x]; i != -1; i = edge[i].next) {int y = edge[i].to;int val = edge[i].val;if (y == father)continue;dis[y] = dis[x] + val;if(dis[y]>maxx){maxx = dis[y];id = y;}dfs(y, x);} } void calcDiameter(){//第一遍dfsmaxx = 0;id = 1;dfs(1, 0);st = id;//第二遍dfsmaxx = 0;dis[st] = 0;dfs(st, 0);ed = id;diameter = maxx; //樹的直徑for (int i = 1; i <= n; i++)disSt[i] = dis[i];dis[ed] = 0;dfs(ed, 0);for (int i = 1; i <= n; i++)disEd[i] = dis[i]; }int main() {scanf("%d", &n);memset(head, -1, sizeof(head));for (int i = 1; i <= n - 1; i++) {int x, y, val;scanf("%d%d%d", &x, &y, &val);addEdge(x, y, val);addEdge(y, x, val);}calcDiameter();printf("%d %d\n", st, ed);printf("%d\n", diameter);return 0; }

2.樹形DP求樹的直徑

設(shè) 1 號(hào)節(jié)點(diǎn)為根，n 個(gè)點(diǎn) n-1 條邊的無向圖就可以看做有根樹

設(shè) dis1[x] 表示從點(diǎn) x 到以 x 為根的子樹中葉結(jié)點(diǎn)的最長(zhǎng)鏈， pos1[x] 表示 dis1[x] 在哪個(gè)點(diǎn)更新；dis2[x] 表示從點(diǎn) x 到以 x 為根的子樹中葉結(jié)點(diǎn)的次長(zhǎng)鏈，pos2[x] 表示 dis2[x] 在哪個(gè)點(diǎn)更新，且要求兩條鏈不能有交集。

這樣一來，對(duì)于任意一點(diǎn) i，經(jīng)過點(diǎn) i 的最長(zhǎng)鏈的分為兩個(gè)部分：i 的最長(zhǎng)鏈 dis1[i]、i 的次長(zhǎng)鏈 dis2[i]

那么，整棵樹的直徑就是

struct Edge {int to, val;int next;Edge(){}Edge(int to,int val,int next):to(to),val(val),next(next){} } edge[N]; int n; int head[N], tot; int dis1[N], dis2[N];//分別維護(hù)第i個(gè)點(diǎn)的最長(zhǎng)鏈、次長(zhǎng)鏈 int pos1[N],pos2[N];//分別維護(hù)dis1[i]、dis2[i]從哪個(gè)點(diǎn)更新 void addEdge(int from, int to, int val) {edge[++tot].to = to;edge[tot].val = val;edge[tot].next = head[from];head[from] = tot; } void dfs(int x, int father) {for (int i = head[x]; i != -1; i = edge[i].next) {int y = edge[i].to;int val = edge[i].val;if (y == father)continue;dfs(y, x);if (dis1[y] + val > dis1[x]) {dis2[x] = dis1[x];dis1[x] = dis1[y] + val;pos2[x] = pos1[x];pos1[x] = y;} else if (dis1[y] + val > dis2[x]) {dis2[x] = dis1[y] + val;pos2[x] = y;}} } int main() {scanf("%d", &n);memset(head, -1, sizeof(head));for (int i = 1; i <= n - 1; i++) {int x, y, val;scanf("%d%d%d", &x, &y, &val);addEdge(x, y, val);addEdge(y, x, val);}dfs(1, 0);int diameter = -INF;for (int i = 1; i <= n; i++)diameter = max(dis1[i] + dis2[i], diameter);printf("%d", diameter);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的树形结构 —— 树与二叉树 —— 树的直径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。