scipy.sparse.csgraph.

connected_components#

scipy.sparse.csgraph.connected_components(csgraph, directed=True, connection='weak', return_labels=True)#

分析稀疏图的连通分量

在 0.11.0 版本中添加。

参数:

csgrapharray_like 或稀疏数组或矩阵: 表示压缩稀疏图的 N x N 矩阵。输入的 csgraph 将被转换为 csr 格式进行计算。
directedbool, 可选: 如果为 True (默认)，则在有向图上操作：仅沿路径 csgraph[i, j] 从点 i 移动到点 j。如果为 False，则在无向图上找到最短路径：算法可以沿 csgraph[i, j] 或 csgraph[j, i] 从点 i 前进到 j。
connectionstr, 可选: ['weak'|'strong']。对于有向图，要使用的连接类型。如果存在从 i 到 j 和从 j 到 i 的路径，则节点 i 和 j 强连接。如果将有向图的所有有向边替换为无向边，则产生的（无向）图是连通的，则该有向图是弱连通的。如果 directed == False，则不引用此关键字。
return_labelsbool, 可选: 如果为 True (默认)，则返回每个连通分量的标签。

返回:

n_components: int: 连通分量的数量。
labels: ndarray: 长度为 N 的连通分量标签数组。

参考文献

[1]

D. J. Pearce, “一种改进的寻找有向图强连通分量的算法”，技术报告，2005

示例

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import connected_components

>>> graph = [
... [0, 1, 1, 0, 0],
... [0, 0, 1, 0, 0],
... [0, 0, 0, 0, 0],
... [0, 0, 0, 0, 1],
... [0, 0, 0, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> print(graph)
<Compressed Sparse Row sparse array of dtype 'int64'
    with 4 stored elements and shape (5, 5)>
    Coords  Values
    (0, 1)  1
    (0, 2)  1
    (1, 2)  1
    (3, 4)  1

>>> n_components, labels = connected_components(csgraph=graph, directed=False, return_labels=True)
>>> n_components
2
>>> labels
array([0, 0, 0, 1, 1], dtype=int32)