maximum_spanning_tree#

maximum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False)[源代码]#

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

参数:
G无向图

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

weightstr

用于边权重的键名。

algorithmstring

查找最大生成树时使用的算法。有效选项为 'kruskal'、'prim' 或 'boruvka'。默认为 'kruskal'。

ignore_nanbool (default: 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.maximum_spanning_tree(G)
>>> sorted(T.edges(data=True))
[(0, 1, {}), (0, 3, {'weight': 2}), (1, 2, {})]
在此页上