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]

Robert E. Tarjan and Uri Zwick, “Finding strong components using depth-first search”, European Journal of Combinatorics, 119, 2024, DOI:10.1016/j.ejc.2023.103815

示例

>>> 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)
本页内容