depth_first_tree#
- scipy.sparse.csgraph.depth_first_tree(csgraph, i_start, directed=True)#
- Return a tree generated by a depth-first search. - Note that a tree generated by a depth-first search is not unique: it depends on the order that the children of each node are searched. - Added in version 0.11.0. - Parameters:
- csgrapharray_like or sparse array or matrix
- The N x N matrix representing the compressed sparse graph. The input csgraph will be converted to csr format for the calculation. 
- i_startint
- The index of starting node. 
- directedbool, optional
- If True (default), then operate on a directed graph: only move from point i to point j along paths csgraph[i, j]. If False, then find the shortest path on an undirected graph: the algorithm can progress from point i to j along csgraph[i, j] or csgraph[j, i]. 
 
- Returns:
- cstreecsr matrix
- The N x N directed compressed-sparse representation of the depth- first tree drawn from csgraph, starting at the specified node. 
 
 - Notes - If multiple valid solutions are possible, output may vary with SciPy and Python version. - Examples - The following example shows the computation of a depth-first tree over a simple four-component graph, starting at node 0: - input graph depth first tree from (0) (0) (0) / \ \ 3 8 8 / \ \ (3)---5---(1) (3) (1) \ / \ / 6 2 6 2 \ / \ / (2) (2) - In compressed sparse representation, the solution looks like this: - >>> from scipy.sparse import csr_array >>> from scipy.sparse.csgraph import depth_first_tree >>> X = csr_array([[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]]) - Note that the resulting graph is a Directed Acyclic Graph which spans the graph. Unlike a breadth-first tree, a depth-first tree of a given graph is not unique if the graph contains cycles. If the above solution had begun with the edge connecting nodes 0 and 3, the result would have been different.