图形的中心点

Question

我在思考如何定位图表的中心点时遇到了一些困难；也就是说，图上的一个节点可以最小化到所有其他节点的最大距离。

例如：

假设我有一个包含 3 个节点的图，排列成一条线（如1-2-3）。

显然，很容易看出该图的中心点是2。我该如何着手实施类似的事情呢？

我知道的唯一算法是 BFS/DFS/Prim's/ 和 Kruskal's。Prim 和 Kruskal 的算法并不真正适用于这种情况。我想我这里需要使用BFS吗？唯一的问题是，BFS 是否会根据您从哪个节点开始返回不同的顺序？

Answer 1

对于相当密集的图：

1. 使用Floyd-Warshall 算法构建所有最短路径矩阵
2. 找到每行中的最大值 - 这是相应顶点（节点）的偏心率
3. 选择具有最小偏心率的顶点 - 它们是中心节点（最小偏心率是图半径）

复杂度 O(V^3)（具有小常数）

如果图稀疏，可以使用每个顶点的 BFS 或Johnson 算法

(O(V^2+ V*E), O(V^2*logV + V*E))

财政年度：

0 1 2   //ecc = 2
1 0 1   //ecc = 1 - central point
2 1 0   //ecc = 2

如果您使用树（正如消失的评论中提到的 MST）-有更快的方法：

1. 来自任意顶点的一个 BFS
2. 找到距最远顶点的另一个 BFS
3. 获取第二个 BFS 最长路径中的中间顶点

O(V+E)