最小生成树#

minimum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False)[source]#

返回无向图 G 上的最小生成树或森林。

参数:
G无向图

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

weightstr

用于边权重的键名。

algorithmstring

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

ignore_nanbool (默认值: False)

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

返回值:
GNetworkX 图

最小生成树或森林。

注意

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

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

可能存在不止一棵具有相同最小或最大权重的树。有关更详细的定义，请参阅 networkx.tree.recognition。

带有自环的孤立节点在树中作为无边的孤立节点存在。

示例

>>> G = nx.cycle_graph(4)
>>> G.add_edge(0, 3, weight=2)
>>> T = nx.minimum_spanning_tree(G)
>>> sorted(T.edges(data=True))
[(0, 1, {}), (1, 2, {}), (2, 3, {})]
在此页上