maximum_spanning_tree

maximum_spanning_tree(G, weight='weight', algorithm='kruskal')[source]

Returns a maximum spanning tree or forest on an undirected graph G.

Parameters:
  • G (undirected graph) – An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.
  • weight (str) – Data key to use for edge weights.
  • algorithm (string) – The algorithm to use when finding a minimum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’.
Returns:

G – A minimum spanning tree or forest.

Return type:

NetworkX Graph

Examples

>>> G = nx.cycle_graph(4)
>>> G.add_edge(0, 3, weight=2)
>>> T = nx.maximum_spanning_tree(G)
>>> sorted(T.edges(data=True))
[(0, 1, {}), (0, 3, {'weight': 2}), (1, 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.

There may be more than one tree with the same minimum or maximum weight. See networkx.tree.recognition for more detailed definitions.