scipy.sparse.csgraph.depth_first_order¶
- scipy.sparse.csgraph.depth_first_order(csgraph, i_start, directed=True, return_predecessors=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] 。
- return_predecessors布尔值，可选
如果为True(默认值)，则返回Prepreesor数组(见下文)。
- 退货
- node_arrayndarray，一维
深度优先的节点列表，从指定节点开始。node_array的长度是可从指定节点到达的节点数。
- predecessorsndarray，一维
仅当RETURN_PREPRECESSERS为True时才返回。深度优先树中每个节点的前置任务的长度为N的列表。如果节点i在树中，则其父节点由前置节点给定 [i] 。如果节点i不在树中(以及父节点)，则前置任务 [i] =-9999。
示例
>>> from scipy.sparse import csr_matrix >>> 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_matrix(graph) >>> print(graph) (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))