scipy.sparse.csgraph.connected_components¶

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

分析稀疏图的连通分量

0.11.0 新版功能.

参数

csgraph类阵列或稀疏矩阵: 表示压缩稀疏图的N×N矩阵。输入的csgraph将转换为CSR格式进行计算。
directed布尔值，可选: 如果为True(默认值)，则对有向图进行操作：仅沿路径csgraph从点i移动到点j [i, j] 。如果为false，则在无向图上查找最短路径：算法可以沿着csgraph从i点前进到j点。 [i, j] 或csgraph [j, i] 。
connection字符串，可选: [‘弱’|‘强’] 。对于有向图，为要使用的连接类型。如果同时存在从i到j和从j到i的路径，则结点i和j是强连通的。如果用无向边替换有向图的所有有向边产生连通(无向)图，则有向图是弱连通的。如果DIRECTED==FALSE，则不引用此关键字。
return_labels布尔值，可选: 如果为True(默认值)，则返回每个连接组件的标签。

退货

N_Components：整型: 连接的组件的数量。
标签：ndarray: 连接组件的标签的长度为N的数组。

参考文献

1: 皮尔斯，“求有向图的强连通分支的一种改进算法”，技术报告，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)
  (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)

压缩稀疏图形例程 (scipy.sparse.csgraph )

scipy.sparse.csgraph.laplacian