首先，我想澄清一下，我已经看到了这个:Finding 'bottleneck edges' in a graph
这不是重复的，只是一个不幸的巧合，那个人错误地将最小切割称为“瓶颈”。
瓶颈边是流网络中的边，在增加时会增加网络的最大流。
所以这不一定是最小割，就像在像 o-1->o-1->o 这样的图的情况下，我们没有瓶颈边，但我们确实有最小割。
(在该示例中，o 是节点，边是 -*->，其中 * 是某个整数。)
无论如何，因此找到所有瓶颈显然可以在 O(V+E) 中完成，(假设该图以邻接列表表示形式给出)，我认为这样做的方法是创建两个大小为 V 的数组，其中我将调用 INCOMING 和 OUTGOING，然后遍历邻接列表的每个元素两次，第一次通过进入每个节点的边的值增加 INCOMING[i]，第二次通过值增加 OUTGOING[j]在每个节点之外，其中 j 是我们正在读取的邻接列表的节点，而 i 是邻接列表中边要到达它的节点。
我认为这在 O(V+E) 时间内有效，但我觉得我的解决方案肯定更复杂且难以解释。有没有更好的解决方案(不比 O(V+E) 好，但更简单？)
最佳答案
您仍然可以使用 Ford-Fulkerson 算法解决此问题。基本上，完成对图的迭代，直到得到最终的(断开连接的)残差图。现在，将有一组可从源 S 到达的节点。 并且将有一组单独的可从接收器 T 到达的节点。
将第一组节点连接到第二组节点的任何边都将是瓶颈边。
为什么这是正确的？试想一下，如果你增加这些边之一的容量，那么你在步骤 1 中得到的最终残差图将不再是最终的残差图，并且仍然会有福特-富克森算法的更多可能迭代。
关于graph - 在 O(V+E) 的图中寻找瓶颈边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50178192/