可以證明從樹的任意一點出發(fā)，所能到達的最遠距離一定是樹的最大直徑的端點。所以兩次bfs(),一次任意一點出發(fā)，一次端點出發(fā)，便能找到最大直徑。

程序代碼如下：（求樹上兩端點的最遠距離）

#include <iostream> #include <string.h> #define MAXN 10005 #define INF 999999999using namespace std;struct Edge {int v, w, next; }edge[MAXN];int head[MAXN], vis[MAXN], d[MAXN], q[MAXN], e, n;int init() {e = 0;memset(head, -1, sizeof(head)); }void add(int u, int v, int w) {edge[e].v = v;edge[e].w = w;edge[e].next = head[u];head[u] = e++; }void bfs(int src) {for （int i = 0; i <= n; i++){vis[i] = 0;d[i] = INF;}int h = 0, t = 0;vis[src] = 1;q[t++] = src;d[src] = 0;while (h < t){int u = q[h++];for (int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;int w = edge[i].w;if (d[u] + w < d[v]){d[v] = d[u] + w;if (!vis[v]){q[t++] = v;vis[v] = 1;}}}} }int main() {int u, v, w;init();cin >> n;for (int i = 1; i <= n - 1; i++){cin >> u >> v >> w;add(u, v, w);add(v, u, w);}bfs(1);int pos = 0, mx = -1;for (int i = 1; i <= n; i++){if(d[i] > mx){mx = d[i];pos = i;}}bfs(pos);mx = -1;for (int i = 1; i <= n; i++){if(d[i] > mx){mx = d[i];}}cout << mx << endl;return 0; }

?

轉載于:https://www.cnblogs.com/lihek/p/3216311.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的树的最长直径（邻接表）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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