maximum_spanning_tree¶
- maximum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False)[source]¶
Returns a maximum spanning tree or forest on an undirected graph
G
.- Parameters
- Gundirected graph
An undirected graph. If
G
is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.- weightstr
Data key to use for edge weights.
- algorithmstring
The algorithm to use when finding a maximum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’.
- ignore_nanbool (default: False)
If a NaN is found as an edge weight normally an exception is raised. If
ignore_nan is True
then that edge is ignored instead.
- Returns
- GNetworkX Graph
A maximum spanning tree or forest.
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.Isolated nodes with self-loops are in the tree as edgeless isolated nodes.
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, {})]