scipy.sparse.csgraph.

connected_components#

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

分析稀疏圖的連通元件

於 0.11.0 版本新增。

參數:

csgraph類陣列或稀疏陣列或矩陣: 代表壓縮稀疏圖的 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, “An Improved Algorithm for Finding the Strongly Connected Components of a Directed Graph”, Technical Report, 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)