在 O(V+E) 的图中查找瓶颈边
Finding Bottleneck Edges in a Graph in O(V+E)
首先，我想澄清一下，我看到了这个：Finding 'bottleneck edges' in a graph
这不是重复的，只是一个不幸的巧合，那个人错误地将最小切割称为 "bottleneck."
瓶颈边是流量网络中的边，增加后会增加网络的最大流量。
所以这不一定是最小割，就像在像 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步中得到的最终残差图将不再是最终的残差图，而且ford-fulkerson算法的迭代还有一种可能。
这个问题可以用Betweenness Centrality来解决。来自 Mark Needham 和 Amy E. Hodler "Graph Algorithms" 第 5 章：
"什么时候应该使用介数中心性？
介数中心性适用于现实世界网络中的广泛问题。我们用它来查找瓶颈、控制点和漏洞。"
该算法计算通过每个节点的最短路径数。较高的中心性被分配给通过它们的最短路径数量较多的节点。它在 Python 包 Networkx 和 Neo4J
中实现
首先，我想澄清一下，我看到了这个：Finding 'bottleneck edges' in a graph
这不是重复的，只是一个不幸的巧合，那个人错误地将最小切割称为 "bottleneck."
瓶颈边是流量网络中的边，增加后会增加网络的最大流量。
所以这不一定是最小割，就像在像 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步中得到的最终残差图将不再是最终的残差图，而且ford-fulkerson算法的迭代还有一种可能。
这个问题可以用Betweenness Centrality来解决。来自 Mark Needham 和 Amy E. Hodler "Graph Algorithms" 第 5 章：
"什么时候应该使用介数中心性？ 介数中心性适用于现实世界网络中的广泛问题。我们用它来查找瓶颈、控制点和漏洞。"
该算法计算通过每个节点的最短路径数。较高的中心性被分配给通过它们的最短路径数量较多的节点。它在 Python 包 Networkx 和 Neo4J
中实现