minimum_spanning_tree#

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

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

Parameters:
G无向图

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

weightstr

用于边权重的数据键。

algorithm字符串

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

ignore_nanbool (默认: False)

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

Returns:
GNetworkX 图

一个最小生成树或森林。

Notes

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

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

可能存在多个具有相同最小或最大权重的树。请参阅 networkx.tree.recognition 以获取更详细的定义。

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

Examples

>>> 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, {})]
On this page