minimum_spanning_edges

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

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

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

参数:

G无向图

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

algorithm字符串

寻找最小生成树时使用的算法。有效选项为 ‘kruskal’、‘prim’ 或 ‘boruvka’。默认为 ‘kruskal’。

weight字符串

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

keys布尔值

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

data布尔值，可选

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

ignore_nan布尔值 (默认值: False)

如果在边权重中找到 NaN，通常会引发异常。如果 ignore_nan is 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 算法，每条边必须有权重属性，且每个边权重必须是唯一的。

对于其他算法，如果图边没有权重属性，将使用默认权重 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.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]]