如何用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行的每个位置(除了位置v2，即其本身)都有一个1而被清楚地标识为图的中心。

即使在E中有其他边的情况下，这也可以识别图的中心。注意，可能有多个中心。。。

图的一个不太严格定义的中心可以被发现为在连通性矩阵中其行中具有最多一个条目的垂直线。

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