使用Numpy或Scipy从邻接矩阵中找到连通分量

Question

我有以下邻接矩阵：

array([[0, 1, 1, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 0, 0],
       [1, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 1, 0, 1, 0],
       [0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 1, 0, 1, 0]])

可以像下面这样绘制:

我的目标是识别连接的图 ABC 和 DEFG。似乎我需要使用深度优先搜索算法，而 Scipy 实现了该算法。下面是我的代码:

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import depth_first_order
import numpy as np

test = np.asarray([
    [0, 1, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0, 1, 0]
])

graph = csr_matrix(test)
result = depth_first_order(graph, 0)

但是我没有得到结果：

>>> result
(array([0, 1, 2]), array([-9999,     0,     1, -9999, -9999, -9999, -9999]))

那是什么 array([-9999, 0, 1, -9999, -9999, -9999, -9999])？此外，在文档中，他们谈论的是一种稀疏矩阵而不是邻接矩阵。但是按定义，邻接矩阵似乎也是一种稀疏矩阵，所以对我来说不太清楚。

- snoob dogg

Answer 1

虽然您确实可以使用DFS查找连通分量，但是SciPy通过scipy.sparse.csgraph.connected_components使其更加容易。以您的示例为例：

In [3]: connected_components(test)                                                              
Out[3]: (2, array([0, 0, 0, 1, 1, 1, 1], dtype=int32))

- fuglede

---

我想补充一个看似显而易见的细节。array([0, 0, 0, 1, 1, 1, 1] 简单地索引了连接组件：0代表ABC，1代表DEFG。在你回答之前，我曾经在寻找这个函数时错过了这一点，可能是因为我的邻接矩阵中只有两个图形。 - snoob dogg

这些标签有什么意义？我不明白如何从标签中检索连接节点的索引。或者它有更大的作用吗？ - Jaswant P

@JaswantP：稍微改述一下snoobdogg已经说过的话，标签表示组件，并由（有序）顶点索引。也就是说，前三个顶点（a、b、c）属于一个组件（0），而另外四个顶点（d、e、f、g）属于另一个组件（1）。 - fuglede

Answer 2

首先，你有一个无向图。再次查看文档，并将directed参数设置为false，因为默认值为True。

你得到的第一个数组是从你开始可达的节点（节点0 = 节点a），包括你的起始节点。 所以你从节点a开始，可以到达b和c。由于你有一个不连通的图，你无法到达其余部分的图。DFS正在执行它应该执行的操作。你需要在d节点上进行DFS，以获取第二个图。

- Yacine Mahdid