minimum_spanning_edges#

minimum_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.minimum_spanning_edges(G, algorithm="kruskal", data=False)
>>> edgelist = list(mst)
>>> sorted(sorted(e) for e in edgelist)
[[0, 1], [1, 2], [2, 3]]

通过 Prim 算法找到最小生成边

>>> 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]]
On this page