### Navigation

- index
- modules |
- modules |
- next |
- previous |
- SciPy v0.12 Reference Guide (DRAFT) »
- Compressed Sparse Graph Routines (`scipy.sparse.csgraph`) »

# scipy.sparse.csgraph.breadth_first_tree

`scipy.sparse.csgraph.``breadth_first_tree`(csgraph, i_start, directed=True)

  Return the tree generated by a breadth-first search

  Note that a breadth-first tree from a specified node is unique.

  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 breadth- first tree drawn from csgraph, starting at the specified node.

  Examples

  The following example shows the computation of a depth-first tree over a simple four-component graph, starting at node 0:

       input graph          breadth first tree from (0)

           (0)                         (0)
          /   \                       /   \
         3     8                     3     8
        /       \                   /       \
      (3)---5---(1)               (3)       (1)
        \       /                           /
         6     2                           2
          \   /                           /
           (2)                         (2)

  In compressed sparse representation, the solution looks like this:

      >>> from scipy.sparse import csr_matrix
      >>> from scipy.sparse.csgraph import breadth_first_tree
      >>> X = csr_matrix([[0, 8, 0, 3],
      ...                 [0, 0, 2, 5],
      ...                 [0, 0, 0, 6],
      ...                 [0, 0, 0, 0]])
      >>> Tcsr = breadth_first_tree(X, 0, directed=False)
      >>> Tcsr.toarray().astype(int)
      array([[0, 8, 0, 3],
             [0, 0, 2, 0],
             [0, 0, 0, 0],
             [0, 0, 0, 0]])

  Note that the resulting graph is a Directed Acyclic Graph which spans the graph. A breadth-first tree from a given node is unique.

### Navigation

- index
- modules |
- modules |
- next |
- previous |
- SciPy v0.12 Reference Guide (DRAFT) »
- Compressed Sparse Graph Routines (`scipy.sparse.csgraph`) »