maximum_spanning_edges

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 – 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.
Return type:

iterator

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)]

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/