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:
- csgrapharray_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_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]. 
- return_predecessorsbool, optional
- If True (default), then return the predecessor array (see below). 
 
- Returns:
- node_arrayndarray, 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. 
- predecessorsndarray, 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))