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) 更好，但更简单？）

4

2 回答 2

7

对于这个问题，您仍然可以使用 Ford-Fulkerson 算法。基本上，完成对图的迭代，直到留下最终的（断开连接的）残差图。现在，将有一组从源 S 可到达的节点。将有一组从汇 T 可到达的单独节点。

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

为什么这是正确的？试想一下，如果您增加其中一条边的容量，那么您在第 1 步中得到的最终残差图将不再是最终残差图，并且福特-富尔克森算法仍有可能进行一次迭代。

于 2019-02-19T21:19:27.687 回答
1

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

“我什么时候应该使用中介中心性？中介中心性适用于现实世界网络中的广泛问题。我们用它来寻找瓶颈、控制点和漏洞。”

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

于 2020-05-14T10:38:40.770 回答