scipy.sparse.csgraph.

breadth_first_order#

scipy.sparse.csgraph.breadth_first_order(csgraph, i_start, directed=True, return_predecessors=True)#

返回以指定節點開始的廣度優先排序。

請注意，廣度優先排序並非唯一，但其產生的樹狀結構是唯一的。

在版本 0.11.0 中新增。

參數:

csgrapharray_like 或稀疏陣列或矩陣: N x N 壓縮稀疏圖。輸入 csgraph 將會轉換為 csr 格式以進行計算。
i_startint: 起始節點的索引。
directedbool，選用: 若為 True (預設)，則對有向圖進行操作：僅沿著路徑 csgraph[i, j] 從點 i 移動到點 j。若為 False，則在無向圖上尋找最短路徑：演算法可以沿著 csgraph[i, j] 或 csgraph[j, i] 從點 i 進展到 j。
return_predecessorsbool，選用: 若為 True (預設)，則返回前導節點陣列 (請參閱下方)。

返回:

node_arrayndarray，一維: 廣度優先節點列表，從指定節點開始。node_array 的長度是從指定節點可到達的節點數量。
predecessorsndarray，一維: 僅在 return_predecessors 為 True 時返回。長度為 N 的列表，其中包含廣度優先樹中每個節點的前導節點。如果節點 i 在樹中，則其父節點由 predecessors[i] 給出。如果節點 i 不在樹中 (且對於父節點)，則 predecessors[i] = -9999。

註解

如果有多個有效的解決方案，則輸出可能會因 SciPy 和 Python 版本而異。

範例

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import breadth_first_order

>>> graph = [
... [0, 1, 2, 0],
... [0, 0, 0, 1],
... [2, 0, 0, 3],
... [0, 0, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> print(graph)
<Compressed Sparse Row sparse array of dtype 'int64'
    with 5 stored elements and shape (4, 4)>
    Coords  Values
    (0, 1)  1
    (0, 2)  2
    (1, 3)  1
    (2, 0)  2
    (2, 3)  3

>>> breadth_first_order(graph,0)
(array([0, 1, 2, 3], dtype=int32), array([-9999,     0,     0,     1], dtype=int32))