networkx.minimum_spanning_tree

minimum_spanning_tree(G)

Generate a minimum spanning tree of an undirected weighted graph.

A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights.

Parameters:

G : NetworkX Graph

Returns:

edges : iterator

A generator that produces edges in the minimum spanning tree. The edges are three-tuples (u,v,w) where w is the weight.

Notes

Uses Kruskal’s algorithm.

If the graph edges do not have a weight attribute a default weight of 1 will be assigned.

Modified code from David Eppstein, April 2006 http://www.ics.uci.edu/~eppstein/PADS/

Examples

>>> G=nx.cycle_graph(4)
>>> G.add_edge(0,3,weight=2) # assign weight 2 to edge 0-3
>>> mst=nx.minimum_spanning_tree(G) # a generator of MST edges
>>> edgelist=list(mst) # make a list of the edges
>>> print sorted(edgelist)
[(0, 1, {'weight': 1}), (1, 2, {'weight': 1}), (2, 3, {'weight': 1})]
>>> T=nx.Graph(edgelist)  # build a graph of the MST.
>>> print sorted(T.edges(data=True))
[(0, 1, {'weight': 1}), (1, 2, {'weight': 1}), (2, 3, {'weight': 1})]