树的最长直径（邻接表）

可以证明从树的任意一点出发，所能到达的最远距离一定是树的最大直径的端点。所以两次bfs(),一次任意一点出发，一次端点出发，便能找到最大直径。

程序代码如下：（求树上两端点的最远距离）

#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年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的树的最长直径（邻接表）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。