树的直径、重心、中心 学习笔记

引入——什么是树？

树是一个简单无环无向连通图，其由 \(n\) 个点与 \(n-1\) 条边组成。它是一种特殊的图。

树的直径

定义

定义树上任意两点之间最长的简单路径为树的直径。

一棵树可能拥有多条直径。

求解

两次 DFS 求法

在没有负边权的情况下，我们一般使用两次 DFS 求树的直径：

第一次 DFS 从任意位置（比如 \(1\)）出发，找到距离最远的点 \(x\)，\(x\) 就是某一条直径的端点之一；
第二次 DFS 从点 \(x\) 出发，找到距离最远的点 \(y\)，\(x\) 到 \(y\) 的路径即为一条直径。