python - 使用 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])？此外，在文档中，他们谈论的是稀疏矩阵而不是邻接矩阵。但是根据定义，邻接矩阵似乎是一个稀疏矩阵，所以我不清楚。

标签： pythonnumpygraphscipy

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