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. - Added in version 0.11.0. - Parameters:
- csgrapharray_like or sparse array or matrix
- The N x N matrix representing the 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]. 
 
- Returns:
- cstreecsr matrix
- The N x N directed compressed-sparse representation of the breadth- 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 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_array >>> from scipy.sparse.csgraph import breadth_first_tree >>> X = csr_array([[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.