maximum_spanning_edges#

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

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

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

Parameters:
G无向图

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

algorithm字符串

用于寻找最大生成树的算法。有效选择包括 ‘kruskal’、’prim’ 或 ‘boruvka’。默认是 ‘kruskal’。

weight字符串

用于权重的边数据键（默认 ‘weight’）。

keys布尔值

是否在多重图中除了边之外还生成边键。如果 G 不是多重图，则忽略此参数。

data布尔值, 可选

如果为 True，则生成边数据以及边。

ignore_nan布尔值 (默认: False)

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

Returns:
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。

Notes

对于 Borůvka 算法，每条边必须有一个权重属性，并且每条边的权重必须不同。

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

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

Examples

>>> 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)  # 将权重 2 分配给边 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]]
On this page