Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

minimum_spanning_edges

minimum_spanning_edges(G, weight='weight', data=True)

Generate edges in a minimum spanning forest of an undirected weighted graph.

A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights. A spanning forest is a union of the spanning trees for each connected component of the graph.

Parameters:

• G (NetworkX Graph) –
• weight (string) – Edge data key to use for weight (default ‘weight’).
• data (bool, optional) – If True yield the edge data along with the edge.

Returns:

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

Return type:

iterator

Examples

>>> G=nx.cycle_graph(4)
>>> G.add_edge(0,3,weight=2) # assign weight 2 to edge 0-3
>>> mst=nx.minimum_spanning_edges(G,data=False) # a generator of MST edges
>>> edgelist=list(mst) # make a list of the edges
>>> print(sorted(edgelist))
[(0, 1), (1, 2), (2, 3)]

Notes

Uses Kruskal’s algorithm.

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

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