scipy.sparse.csgraph.

depth_first_order#

scipy.sparse.csgraph.depth_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 depth_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

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