scipy.sparse.csgraph.

connected_components

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

分析稀疏图的连通分量

Added in version 0.11.0.

参数:

csgraph类似数组或稀疏矩阵

表示压缩稀疏图的 N x N 矩阵。输入的 csgraph 将被转换为 csr 格式进行计算。

有向的bool, 可选

如果为 True（默认），则在有向图上操作：仅沿路径 csgraph[i, j] 从点 i 移动到点 j。如果为 False，则在无向图上找到最短路径：算法可以从点 i 到点 j 沿 csgraph[i, j] 或 csgraph[j, i] 前进。

连接str, 可选

[‘弱’|’强’]。对于有向图，使用的连接类型。如果从节点 i 到节点 j 和从节点 j 到节点 i 都存在路径，则节点 i 和 j 是强连接的。如果将其所有有向边替换为无向边后生成一个连通（无向）图，则有向图是弱连接的。如果 directed == False，则不引用此关键字。

return_labelsbool, 可选

如果为 True（默认），则返回每个连通分量的标签。

返回:

n_components: int

连接组件的数量。

标签: ndarray

连接组件的标签的长度为N的数组。

参考文献

[1]

D. J. Pearce, “An Improved Algorithm for Finding the Strongly Connected Components of a Directed Graph”, Technical Report, 2005

示例

Try it in your browser!

>>> from scipy.sparse import csr_matrix
>>> 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_matrix(graph)
>>> print(graph)
<Compressed Sparse Row sparse matrix 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)

Go BackOpen In Tab