minimum_spanning_tree#
- scipy.sparse.csgraph.minimum_spanning_tree(csgraph, overwrite=False)#
- Return a minimum spanning tree of an undirected graph - A minimum spanning tree is a graph consisting of the subset of edges which together connect all connected nodes, while minimizing the total sum of weights on the edges. This is computed using the Kruskal algorithm. - Added in version 0.11.0. - Parameters:
- csgrapharray_like or sparse array or matrix, 2 dimensions
- The N x N matrix representing an undirected graph over N nodes (see notes below). 
- overwritebool, optional
- If true, then parts of the input graph will be overwritten for efficiency. Default is False. 
 
- Returns:
- span_treecsr matrix
- The N x N compressed-sparse representation of the undirected minimum spanning tree over the input (see notes below). 
 
 - Notes - This routine uses undirected graphs as input and output. That is, if graph[i, j] and graph[j, i] are both zero, then nodes i and j do not have an edge connecting them. If either is nonzero, then the two are connected by the minimum nonzero value of the two. - This routine loses precision when users input a dense matrix. Small elements < 1E-8 of the dense matrix are rounded to zero. All users should input sparse matrices if possible to avoid it. - If the graph is not connected, this routine returns the minimum spanning forest, i.e. the union of the minimum spanning trees on each connected component. - If multiple valid solutions are possible, output may vary with SciPy and Python version. - Examples - The following example shows the computation of a minimum spanning tree over a simple four-component graph: - input graph minimum spanning tree (0) (0) / \ / 3 8 3 / \ / (3)---5---(1) (3)---5---(1) \ / / 6 2 2 \ / / (2) (2) - It is easy to see from inspection that the minimum spanning tree involves removing the edges with weights 8 and 6. In compressed sparse representation, the solution looks like this: - >>> from scipy.sparse import csr_array >>> from scipy.sparse.csgraph import minimum_spanning_tree >>> X = csr_array([[0, 8, 0, 3], ... [0, 0, 2, 5], ... [0, 0, 0, 6], ... [0, 0, 0, 0]]) >>> Tcsr = minimum_spanning_tree(X) >>> Tcsr.toarray().astype(int) array([[0, 0, 0, 3], [0, 0, 2, 5], [0, 0, 0, 0], [0, 0, 0, 0]])