maximum_spanning_edges

maximum_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 是真的还是 (u, v) 如果 data 是假的。

笔记

对于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.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]]