algorithm - 图的中心点

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 或约翰逊算法

(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)

Answer 2

Python 模块NetworkX提供了这样的 API center(G, e=None)。参考它的源代码这里的实现。

以佛罗伦萨家庭图为例，中心节点为红色。

---

import networkx as nx

G = nx.florentine_families_graph()
center_nodes = nx.center(G)