networkx.maximum_spanning_edges¶

networkx.maximum_spanning_edges(G, algorithm='kruskal', weight='weight', data=True)[source]¶

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

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

Parameters:

G : undirected Graph An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found. algorithm : string The algorithm to use when finding a maximum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’. weight : string Edge data key to use for weight (default ‘weight’). keys : bool Whether to yield edge key in multigraphs in addition to the edge. If G is not a multigraph, this is ignored. data : bool, optional If True yield the edge data along with the edge.

Returns:

edges : iterator An iterator over tuples representing edges in a maximum spanning tree of G. If G is a multigraph and both keys and data are True, then the tuples are four-tuples of the form (u, v, k, w), where (u, v) is an edge, k is the edge key identifying the particular edge joining u with v, and w is the weight of the edge. If keys is True but data is False, the tuples are three-tuples of the form (u, v, k). If G is not a multigraph, the tuples are of the form (u, v, w) if data is True or (u, v) if data is False.

Notes

For Borůvka’s algorithm, each edge must have a weight attribute, and each edge weight must be distinct.

For the other algorithms, 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/

Examples

>>> from networkx.algorithms import tree

Find maximum spanning edges by Kruskal’s algorithm

>>> G = nx.cycle_graph(4)
>>> G.add_edge(0, 3, weight=2)
>>> mst = tree.maximum_spanning_edges(G, algorithm='kruskal', data=False)
>>> edgelist = list(mst)
>>> sorted(edgelist)
[(0, 1), (0, 3), (1, 2)]

Find maximum spanning edges by Prim’s algorithm

>>> G = nx.cycle_graph(4)
>>> G.add_edge(0,3,weight=2) # assign weight 2 to edge 0-3
>>> mst = tree.maximum_spanning_edges(G, algorithm='prim', data=False)
>>> edgelist = list(mst)
>>> sorted(edgelist)
[(0, 1), (0, 3), (3, 2)]