scipy.sparse.csgraph.

breadth_first_tree#

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

傳回由廣度優先搜尋產生的樹狀結構

請注意，從指定節點開始的廣度優先樹狀結構是唯一的。

在版本 0.11.0 中新增。

參數:

csgraph類陣列 (array-like) 或稀疏陣列或矩陣: 代表壓縮稀疏圖的 N x N 矩陣。輸入 csgraph 將轉換為 csr 格式以進行計算。
i_start整數: 起始節點的索引。
directed布林值，選用: 如果為 True (預設值)，則對有向圖進行操作：僅沿著路徑 csgraph[i, j] 從點 i 移動到點 j。如果為 False，則在無向圖上尋找最短路徑：演算法可以沿著 csgraph[i, j] 或 csgraph[j, i] 從點 i 進展到點 j。

傳回值:

cstreecsr 矩陣: 從 csgraph 繪製的廣度優先樹狀結構，從指定節點開始的 N x N 有向壓縮稀疏表示。

註解

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

範例

以下範例展示了在一個簡單的四組件圖上計算深度優先樹狀結構，從節點 0 開始

 input graph          breadth first tree from (0)

     (0)                         (0)
    /   \                       /   \
   3     8                     3     8
  /       \                   /       \
(3)---5---(1)               (3)       (1)
  \       /                           /
   6     2                           2
    \   /                           /
     (2)                         (2)

在壓縮稀疏表示法中，解法看起來像這樣

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import breadth_first_tree
>>> X = csr_array([[0, 8, 0, 3],
...                [0, 0, 2, 5],
...                [0, 0, 0, 6],
...                [0, 0, 0, 0]])
>>> Tcsr = breadth_first_tree(X, 0, directed=False)
>>> Tcsr.toarray().astype(int)
array([[0, 8, 0, 3],
       [0, 0, 2, 0],
       [0, 0, 0, 0],
       [0, 0, 0, 0]])

請注意，結果圖是一個跨越圖的有向無環圖 (Directed Acyclic Graph)。從給定節點開始的廣度優先樹狀結構是唯一的。