`scipy.sparse.csgraph._traversal:breadth_first_order`

Signature

   def     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.

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).

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.

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

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)

✗

breadth_first_order(graph,0)

✓