java - 如何使用java找到图的中心（顶点，与其他所有顶点相连，但边指向图的中心）

Question

如何使用java找到图的中心（顶点，与其他所有顶点相连，但边指向图的中心）。它对 facebook 之类的网站非常有用。

Answer 1

假设您有一个带有一组 V 顶点的图：

V = { v1, v2, v3, ... , vn }

现在考虑所有顶点都连接到 v2 并且不存在其他边的极端情况，即作为元组 (from, to) 给出的边集 E 是：

E = ( (v1, v2), (v3, v2), ... , (vn, v2) }

在这种极端情况下，v2 显然是您定义的图形的中心。

连接矩阵 A 如下所示：

A = {
   from
to  v1, v2, v3, ..  vn
v1   0   0   0  ..   0    
v2   1   0   1  ..   1
v3   0   0   0  ..   0    
   :               :
vn   0   0   0  ..   0 }

这里 v2 通过在其连接矩阵 A 的行的每个位置（除了 pos v2，即其自身）都有一个，清楚地标识为图的中心。

即使在 E 中还有其他边时，这也可以识别图形的中心。请注意，可能有多个中心......

可以找到图的不太严格定义的中心作为连接矩阵中其行中具有最多一个条目的顶点。

您可以避免构造矩阵 A，当您拥有集合 E 并且只计算每个顶点出现在边缘元组的 to 位置的次数时。具有最大计数的顶点是图中定义模糊的中心，或者计数为 n - 1 的顶点是您严格定义的中心。