Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# networkx.algorithms.tree.mst.minimum_spanning_edges¶

minimum_spanning_edges(G, algorithm='kruskal', weight='weight', keys=True, data=True, ignore_nan=False)[source]

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.

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 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 G is 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 True then that edge is ignored instead. edges – An iterator over edges in a maximum spanning tree of G. Edges connecting nodes u and v are represented as tuples: (u, v, k, d) or (u, v, k) or (u, v, d) or (u, v) If G is a multigraph, keys indicates whether the edge key k will be reported in the third position in the edge tuple. data indicates whether the edge datadict d will appear at the end of the edge tuple. If G is not a multigraph, the tuples are (u, v, d) if data is True or (u, v) if data is False. iterator

Examples

>>> from networkx.algorithms import tree


Find minimum spanning edges by Kruskal’s algorithm

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


Find minimum spanning edges by Prim’s algorithm

>>> G = nx.cycle_graph(4)