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

问题描述

首先，我想澄清一下我看到的情况：Finding 'bottleneck edges' in a graph

而且这并不是重复，只是不幸的巧合，那个人错误地将Minin-Cut称为"瓶颈"。

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

所以这不一定是最小割，就像o-1->o-1->o这样的图一样，我们没有瓶颈边，但我们确实有最小割。

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

总之，查找所有瓶颈显然可以在O(V+E)中完成(假设图是以邻接列表表示形式给出的)，我认为这样做的方法是创建两个大小为V的数组，我将其称为传入和传出，然后遍历邻接列表的每个元素两次，第一次将传入[i]增加到进入每个节点的边的值，第二次增加传出[j]到每个节点的传出的值，其中j是我们正在读取的邻接列表的节点，I是邻接列表中要指向它的边的节点。

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

推荐答案

您仍然可以使用福特-富尔克森算法来解决此问题。基本上，完成对该图的迭代，直到得到最终的(断开连接的)残差图。现在，将有一组可以从源S到达的节点，并且将有一组单独的可以从宿T到达的节点。

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

为什么这是正确的？试想一下，如果您增加了其中一条边的容量，那么在步骤1中得到的最终残差图将不再是最终残差图，并且仍然会有一次可能的Ford-Fulkerson算法迭代。

这篇关于在O(V+E)中寻找图的瓶颈边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！