代码之家 › 专栏 › 技术社区 › nedlaback

在O(V+E)图中寻找瓶颈边

network-flow graph-theory graph

4

nedlaback · 技术社区 · 7 年前

首先,我想澄清一下,我已经看到了这一点: Finding 'bottleneck edges' in a graph

这并不是重复的,只是一个不幸的巧合,那个人错误地称min cut为“瓶颈”

瓶颈边是流量网络中的一条边,它在增加时会增加网络的最大流量。

因此,这并不一定是最小割,就像o-1->o-1->o、我们没有瓶颈边缘,但我们有一个最小切割。

(在该示例中,o是节点,边是-*->,其中*是某个整数。)

无论如何,显然可以在O(V+E)中找到所有瓶颈,(假设该图是用邻接列表表示的),我认为这样做的方法是创建两个大小为V的数组,我将其称为传入和传出,然后在邻接列表的每个元素中迭代两次,第一次通过每个节点的边值增加传入[I],第二次,用每个节点的输出值来增加输出[j],其中j是我们正在读取的邻接列表中的节点,i是邻接列表中边到它的节点。

我认为这在O(V+E)时间内有效,但我觉得我的解决方案肯定更复杂,更难以解释。是否有更好的解决方案(不比O(V+E)更好,但更简单?)

2 回复 | 直到 7 年前

1

7

RafiyaJaved 6 年前

对于这个问题,您仍然可以使用Ford-Fulkerson算法。基本上,完成对图的迭代,直到剩下最后一个(断开连接的)残差图。现在,将有一组可以从源S访问的节点。将有一组单独的节点可以从接收器T访问。

将第一组节点连接到第二组节点的任何边都将是瓶颈边。

为什么这是正确的?试想一下,如果您增加了其中一条边的容量,那么您在步骤1中得到的最终残差图将不再是最终残差图,而且还会有一个福特-富尔克森算法的可能迭代。

2

1

Bat1985 4 年前

这个问题可以用中介中心性来解决。来自Mark Needham&Amy E.Hodler“图形算法”第5章:

“何时应该使用中间性中心性? 介数中心性适用于现实网络中的广泛问题。我们用它来寻找瓶颈、控制点和漏洞。“”

该算法计算通过每个节点的最短路径数。将更高的中心性分配给通过它们的最短路径数量更多的节点。它是在Python包中实现的 Networkx Neo4J也是如此