Depth-first search explores as far as possible along each branch before backtracking, in contrast to breadth-first search, which explores all of a node's immediate neighbors before moving further out — depth_first_order() returns the array of node indices in the order DFS actually visited them starting from i_start, plus an array of each visited node's predecessor in the resulting traversal tree. Nodes that aren't reachable from i_start at all are simply never included in the returned visiting order.
1Understanding csgraph.depth_first_order()
Depth-first search explores as far as possible along each branch before backtracking, in contrast to breadth-first search, which explores all of a node's immediate neighbors before moving further out — depth_first_order() returns the array of node indices in the order DFS actually visited them starting from i_start, plus an array of each visited node's predecessor in the resulting traversal tree. Nodes that aren't reachable from i_start at all are simply never included in the returned visiting order.
Nodes unreachable from the given starting node i_start are silently excluded from depth_first_order()'s result entirely — check the length of the returned order array against the graph's total node count if you need to detect unreached nodes explicitly.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import depth_first_order
graph = csr_matrix([[0, 1, 1], [0, 0, 0], [0, 0, 0]])
order, predecessors = depth_first_order(graph, i_start=0)
print(order)2Practical Example
Here is a real-world application of csgraph.depth_first_order() showing how it is used in production SciPy code.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import depth_first_order
graph = csr_matrix([[0, 1, 0], [0, 0, 1], [0, 0, 0]])
order, predecessors = depth_first_order(graph, i_start=0)
print(order)
print(predecessors)3Best Practices
Follow these guidelines when working with csgraph.depth_first_order():
1. Use depth_first_order() when you specifically need a depth-first traversal order, such as for topological-sort-style processing or exploring one path deeply before others
2. Check the returned order array's length against the total number of nodes to detect any nodes that weren't reachable from the given starting point
3. Use the returned predecessors array to reconstruct the actual traversal tree/path taken to reach any specific visited node
Tip: Nodes unreachable from the given starting node i_start are silently excluded from depth_first_order()'s result entirely — check the length of the returned order array against the graph's total node count if you need to detect unreached nodes explicitly.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import depth_first_order
graph = csr_matrix([[0, 1, 1], [0, 0, 0], [0, 0, 0]])
order, predecessors = depth_first_order(graph, i_start=0)
print(order)