Skip to main content
`Ctrl`+`K`
scipy.sparse.csgraph.

# breadth_first_order

scipy.sparse.csgraph.breadth_first_order(csgraph, i_start, directed=True, return_predecessors=True)

  Return a breadth-first ordering starting with specified node.

  Note that a breadth-first order is not unique, but the tree which it generates is unique.

  Added in version 0.11.0.

  Parameters:
    csgraph array_like or sparse array or matrix

      The N x N 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].

    return_predecessors bool, optional

      If True (default), then return the predecessor array (see below).

  Returns:
    node_array ndarray, one dimension

      The breadth-first list of nodes, starting with specified node. The length of node_array is the number of nodes reachable from the specified node.

    predecessors ndarray, one dimension

      Returned only if return_predecessors is True. The length-N list of predecessors of each node in a breadth-first tree. If node i is in the tree, then its parent is given by predecessors[i]. If node i is not in the tree (and for the parent node) then predecessors[i] = -9999.

  Notes

  If multiple valid solutions are possible, output may vary with SciPy and Python version.

  Examples

      >>> from scipy.sparse import csr_array
      >>> from scipy.sparse.csgraph import breadth_first_order

      >>> graph = [
      ... [0, 1, 2, 0],
      ... [0, 0, 0, 1],
      ... [2, 0, 0, 3],
      ... [0, 0, 0, 0]
      ... ]
      >>> graph = csr_array(graph)
      >>> print(graph)
      <Compressed Sparse Row sparse array of dtype 'int64'
          with 5 stored elements and shape (4, 4)>
          Coords  Values
          (0, 1)  1
          (0, 2)  2
          (1, 3)  1
          (2, 0)  2
          (2, 3)  3

      >>> breadth_first_order(graph,0)
      (array([0, 1, 2, 3], dtype=int32), array([-9999,     0,     0,     1], dtype=int32))