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 bothkeys
anddata
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 joiningu
withv
, andw
is the weight of the edge. Ifkeys
is True butdata
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)
ifdata
is True or(u, v)
ifdata
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/
- G (undirected Graph) – An undirected graph. If