scipy.sparse.csgraph.depth_first_tree¶
- scipy.sparse.csgraph.depth_first_tree(csgraph, i_start, directed=True)¶
返回深度优先搜索生成的树。
请注意，深度优先搜索生成的树不是唯一的：它取决于搜索每个节点的子节点的顺序。
0.11.0 新版功能.
- 参数
- csgraph类阵列或稀疏矩阵
表示压缩稀疏图的N×N矩阵。输入的csgraph将转换为CSR格式进行计算。
- i_start集成
起始节点的索引。
- directed布尔值，可选
如果为True(默认值)，则对有向图进行操作：仅沿路径csgraph从点i移动到点j [i, j] 。如果为false，则在无向图上查找最短路径：算法可以沿着csgraph从i点前进到j点。 [i, j] 或csgraph [j, i] 。
- 退货
- cstreeCSR矩阵
从指定节点开始从csgraph绘制的深度优先树的N x N有向压缩稀疏表示形式。
示例
下面的示例显示了从节点0开始在简单的四分量图上计算深度优先树的过程：
input graph depth first tree from (0) (0) (0) / \ \ 3 8 8 / \ \ (3)---5---(1) (3) (1) \ / \ / 6 2 6 2 \ / \ / (2) (2)
在压缩稀疏表示中，解决方案如下所示：
>>> from scipy.sparse import csr_matrix >>> from scipy.sparse.csgraph import depth_first_tree >>> X = csr_matrix([[0, 8, 0, 3], ... [0, 0, 2, 5], ... [0, 0, 0, 6], ... [0, 0, 0, 0]]) >>> Tcsr = depth_first_tree(X, 0, directed=False) >>> Tcsr.toarray().astype(int) array([[0, 8, 0, 0], [0, 0, 2, 0], [0, 0, 0, 6], [0, 0, 0, 0]])
请注意，结果图是横跨该图的有向无环图。与广度优先树不同，如果图包含圈，则给定图的深度优先树不是唯一的。如果上述解决方案是从连接节点0和3的边开始的，则结果会有所不同。