Generate a minimum spanning tree of an undirected graph.
Uses Kruskal’s algorithm.
| Parameters: | G : NetworkX Graph |
|---|---|
| Returns: | A generator that produces edges in the minimum spanning tree. : The edges are three-tuples (u,v,w) where w is the weight. : |
Notes
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.kruskal_mst(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})]