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

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

network-flow graph-theory graph

nedlaback · 技术社区 · 6 年前

首先,我想澄清一下,我已经看到了这一点: 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 回复 | 直到 6 年前

RafiyaJaved 6 年前

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

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

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

Bat1985 4 年前

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

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

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

推荐文章

amonroejj · 实现基于节点的工作流的一般原则,如Unreal、Blender、Alteryx等?

7 年前

quantummidget · 正在查找BFS父关系数组

7 年前

I'm not human · Prolog查找不相关的图形节点

7 年前

WIZARD_ · 无向非加权图的最大顶点对数

7 年前

user9137770 · 邻接列表与邻接矩阵的区别

7 年前

Parth Prajapati · java中的哪个标准库数据结构为实现邻接列表提供了最短的复杂时间?[已关闭]

7 年前

Sook Yee Lim · 在给定邻接矩阵的情况下求两个图的交并?

7 年前

DK100 · 在广度优先搜索中处理重复节点

7 年前

Keith Pham · 最大化给定预算的子图“价值”

7 年前

Mathochist · 在配对列表中查找最大配对数

7 年前