stoer_wagner

stoer_wagner(G, weight='weight', heap=<class 'networkx.utils.heaps.BinaryHeap'>)

使用Stoer-Wagner算法返回加权最小切边。

使用Stoer-Wagner算法确定连接图的最小切边。在加权的情况下，所有权重都必须是非负的。

算法的运行时间取决于所用堆的类型：

堆类型	运行时间
二元堆	\(O(n (m + n) \log n)\)
斐波那契堆	\(O(nm + n^2 \log n)\)
成对堆	\(O(2^{2 \sqrt{\log \log n}} nm + n^2 \log n)\)

参数

G网络X图表

图形的边应该有一个由下面的权重参数命名的属性。如果该属性不存在，则认为该边具有单位权重。

weight字符串

边的权重属性的名称。如果该属性不存在，则假定单位重量。缺省值：‘权重’。

heap班级

算法中要使用的堆的类型。它应该是的子类 MinHeap 或者实现兼容的接口。

如果要使用库存堆实现， BinaryHeap 建议结束 PairingHeap 对于没有优化属性访问（如cpython）的Python实现，尽管运行时间较慢。对于具有优化属性访问（例如pypy）的python实现， PairingHeap 提供更好的性能。默认值： BinaryHeap .

返回

cut_value整型或浮点型

最小切割中边的权重之和。

partition一对节点列表

定义最小割集的节点分区。

加薪

NetworkXNotImplemented

如果图是有向图或多重图。

NetworkXError

如果图的节点少于两个、未连接或具有负权重边。

实例

>>> G = nx.Graph()
>>> G.add_edge("x", "a", weight=3)
>>> G.add_edge("x", "b", weight=1)
>>> G.add_edge("a", "c", weight=3)
>>> G.add_edge("b", "c", weight=5)
>>> G.add_edge("b", "d", weight=4)
>>> G.add_edge("d", "e", weight=2)
>>> G.add_edge("c", "y", weight=2)
>>> G.add_edge("e", "y", weight=3)
>>> cut_value, partition = nx.stoer_wagner(G)
>>> cut_value
4