maximum_spanning_edges#

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

生成无向加权图的最大生成森林中的边。

最大生成树是图的一个子图（一棵树），其边权重的总和最大。生成森林是图中每个连通分量的生成树的并集。

参数:
G无向图

一个无向图。如果 G 是连通的，算法将找到一棵生成树。否则，将找到一个生成森林。

algorithm字符串

用于查找最大生成树的算法。有效选项包括 'kruskal'、'prim' 或 'boruvka'。默认值为 'kruskal'。

weight字符串

用于权重的边数据键（默认为 'weight'）。

keys布尔值

对于多重图，是否在边之外产生边键。如果 G 不是多重图，则忽略此项。

data布尔值，可选

如果为 True，则与边一起产生边数据。

ignore_nan布尔值（默认为 False）

如果在边权重中发现 NaN，通常会引发异常。如果 ignore_nan 为 True，则该边将被忽略。

返回:
edges迭代器

一个迭代器，遍历 G 的最大生成树中的边。连接节点 u 和 v 的边表示为元组：(u, v, k, d) 或 (u, v, k) 或 (u, v, d) 或 (u, v)

如果 G 是多重图，keys 指示是否在边元组的第三个位置报告边键 k。data 指示边数据字典 d 是否出现在边元组的末尾。

如果 G 不是多重图，则元组为 (u, v, d)（如果 data 为 True）或 (u, v)（如果 data 为 False）。

注意

对于 Borůvka 算法，每条边必须具有 weight 属性，并且每个边权重必须唯一。

对于其他算法，如果图的边没有 weight 属性，将使用默认权重 1。

改编自 David Eppstein 的代码，2006年4月 http://www.ics.uci.edu/~eppstein/PADS/

示例

>>> from networkx.algorithms import tree

使用 Kruskal 算法查找最大生成边

>>> 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(sorted(e) for e in edgelist)
[[0, 1], [0, 3], [1, 2]]

使用 Prim 算法查找最大生成边

>>> 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(sorted(e) for e in edgelist)
[[0, 1], [0, 3], [2, 3]]
在本页