stoer_wagner#

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

使用 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)\)
参数:
GNetworkX 图

图的边应具有由下面的 weight 参数指定的属性。如果此属性不存在，则该边被视为具有单位权重。

weight字符串

边的权重属性名称。如果该属性不存在，则假定单位权重。默认值：'weight'。

heap类

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

如果使用标准堆实现，对于没有优化属性访问的 Python 实现（例如 CPython），尽管渐近运行时间较慢，仍推荐使用 BinaryHeap 而非 PairingHeap。对于优化了属性访问的 Python 实现（例如 PyPy），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
本页内容