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 强连通，如果从 i 到 j 以及从 j 到 i 都存在路径。有向图是弱连通的，如果将所有有向边替换为无向边会产生一个连通的（无向）图。如果 directed == False，则不引用此关键字。
return_labelsbool, 可选: 如果为 True（默认），则返回每个连通分量的标签。

返回值:

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

参考文献

[1]

D. J. Pearce，"寻找有向图强连通分量的改进算法"，技术报告，2005 年

示例

>>> 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)
  (np.int32(0), np.int32(1))        1
  (np.int32(0), np.int32(2))        1
  (np.int32(1), np.int32(2))        1
  (np.int32(3), np.int32(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)