寻找无向无权图中最小最大距离节点（图中心）的高效算法

你提到的O(N*(N+E))方法是对每个节点做一次BFS/DFS计算最远节点距离，确实能找到中心，但节点数较多时效率很低。存在时间复杂度为**O(N+E)**的线性时间算法，核心思路是利用图的直径特性推导中心：

算法步骤 #

• 第一步：任选一个节点s，用BFS找到距离s最远的节点u
• 第二步：从u出发做BFS，找到距离u最远的节点v，此时u-v的路径就是图的直径（图中最长的最短路径）
• 第三步：分别从u和v出发做BFS，记录每个节点到u的距离dist_u[x]、到v的距离dist_v[x]。对每个节点x，其到所有节点的最大距离为max(dist_u[x], dist_v[x])，找到这个值最小的节点，就是图的中心

原理说明 #

无向无权图的中心必然位于直径的路径上，且任意节点的最远节点一定是直径的两个端点之一。因此用max(dist_u[x], dist_v[x])就能准确得到该节点的最大距离（即离心率），再筛选出离心率最小的节点即可，全程仅需3次BFS，时间复杂度线性，远优于逐个节点遍历的方法。

内容的提问来源于stack exchange，提问作者user21251001