Skip to main content
`Ctrl`+`K`

# scipy.sparse.csgraph.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.

  New in version 0.11.0.

  Parameters:
    csgraph array_like or sparse matrix

      The N x N matrix representing the compressed sparse graph. The input csgraph will be converted to csr format for the calculation.

    i_start int

      The index of starting node.

    directed bool, 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:
    cstree csr 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_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]])

  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.