题目地址：

https://www.lintcode.com/problem/longest-path-on-the-tree/description

给定一棵有$n$个顶点的无向带权图，其具有树性质。求其直径。

思路是，先用BFS从任意一个点$v$开始对图进行遍历，找到离$v$最远的那个顶点$u$，然后再从$u$开始BFS，找到离$u$最远的顶点，这个距离就是直径。之所以不用DFS是因为容易爆栈。

算法正确性证明： 对图的顶点个数进行归纳。如果图只有$1$或者$2$个顶点，算法正确。如果有$n$个顶点，假设第一次BFS的时候是从$v$开始遍历的，如果有直径通过$v$，那么算法显然成立；如果所有直径都不通过$v$，那么其必在去掉$v$后产生的若干个连通分量的其中一个里。设这些连通分量的“入口”分别是$x_1,...,x_r$，由归纳假设，这些连通分量每一个的直径都存在一个点$y_1,...,y_r$使得它们都是在各自连通分量里离$x_i$最远的点。而这些点必然有其中一个是离$v$最远的。所以直径的一个端点必然能被算法搜出来。所以算法正确。

代码如下：

import java.util.*; public class Solution { /** * @param n: The number of nodes * @param starts: One point of the edge * @param ends: Another point of the edge * @param lens: The length of the edge * @return: Return the length of longest path on the tree. */ public int longestPath(int n, int[] starts, int[] ends, int[] lens) { // Write your code here Map<Integer, List<int[]>> graph = buildGraph(starts, ends, lens); int[] res = bfs(0, graph, n); return bfs(res[0], graph, n)[1]; } // 从start顶点开始bfs，返回一个长度为2的数组res， // res[0]表示离start最远的点的编号，res[1]表示其离start的距离 private int[] bfs(int start, Map<Integer, List<int[]>> graph, int n) { int[] res = {0, 0}; boolean[] visited = new boolean[n]; visited[start] = true; // 由于是树，所以可以直接用普通的队列而不是优先队列，因为树的两个顶点的路径是唯一的 Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{start, 0}); while (!queue.isEmpty()) { int[] cur = queue.poll(); for (int[] next : graph.get(cur[0])) { if (visited[next[0]]) { continue; } visited[next[0]] = true; if (cur[1] + next[1] > res[1]) { res[0] = next[0]; res[1] = cur[1] + next[1]; } queue.offer(new int[]{next[0], cur[1] + next[1]}); } } return res; } private Map<Integer, List<int[]>> buildGraph(int[] starts, int[] ends, int[] lens) { Map<Integer, List<int[]>> graph = new HashMap<>(); for (int i = 0; i < starts.length; i++) { graph.computeIfAbsent(starts[i], k -> new ArrayList<>()).add(new int[]{ends[i], lens[i]}); graph.computeIfAbsent(ends[i], k -> new ArrayList<>()).add(new int[]{starts[i], lens[i]}); } return graph; } }

时空复杂度$O(n)$。