在O（V+E）时间复杂度下找到图中的瓶颈边

Question

在O（V+E）时间复杂度下找到图中的瓶颈边

graphgraph-theorynetwork-flow

4

首先，我想澄清一下，我看到了这个链接：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）更好，而是更简单的解决方案？）

- nedlaback

2个回答

1

这个问题可以通过介数中心性来解决。引自Mark Needham和Amy E. Hodler的《图算法》第5章：

“何时应该使用介数中心性？介数中心性适用于现实世界网络中的各种问题。我们使用它来查找瓶颈、控制点和漏洞。”

该算法计算通过每个节点的最短路径数量。具有更多最短路径通过的节点被分配更高的中心性。它在Python包Networkx和Neo4J中实现。

- Bat1985

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- RafiyaJaved · Accepted Answer

你可以仍然使用Ford-Fulkerson算法解决这个问题。基本上，不断迭代图形，直到最终（不连通的）剩余图形。现在，将有一组从源S可达的节点。还将有一组单独的节点可以从汇T到达。

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

为什么这是正确的？想象一下，如果你增加了其中一个边缘的容量，那么你在步骤1中得到的最终剩余图就不再是最终剩余图，而且Ford-Fulkerson算法还有一次可能的迭代。