minimum_spanning_edges(G, algorithm='kruskal', weight='weight', keys=True, data=True, ignore_nan=False)¶
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.
G (undirected Graph) – An undirected graph. If
Gis connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.
algorithm (string) – The algorithm to use when finding a minimum 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
Gis not a multigraph, this is ignored.
data (bool, optional) – If True yield the edge data along with the edge.
ignore_nan (bool (default: False)) – If a NaN is found as an edge weight normally an exception is raised. If
ignore_nan is Truethen that edge is ignored instead.
edges – An iterator over edges in a maximum spanning tree of
G. Edges connecting nodes
vare represented as tuples:
(u, v, k, d)or
(u, v, k)or
(u, v, d)or
Gis a multigraph,
keysindicates whether the edge key
kwill be reported in the third position in the edge tuple.
dataindicates whether the edge datadict
dwill appear at the end of the edge tuple.
Gis not a multigraph, the tuples are
(u, v, d)if
datais True or
- Return type
>>> from networkx.algorithms import tree
Find minimum spanning edges by Kruskal’s algorithm
>>> G = nx.cycle_graph(4) >>> G.add_edge(0, 3, weight=2) >>> mst = tree.minimum_spanning_edges(G, algorithm="kruskal", data=False) >>> edgelist = list(mst) >>> sorted(sorted(e) for e in edgelist) [[0, 1], [1, 2], [2, 3]]
Find minimum spanning edges by Prim’s algorithm
>>> G = nx.cycle_graph(4) >>> G.add_edge(0, 3, weight=2) >>> mst = tree.minimum_spanning_edges(G, algorithm="prim", data=False) >>> edgelist = list(mst) >>> sorted(sorted(e) for e in edgelist) [[0, 1], [1, 2], [2, 3]]
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/