使用最大流算法查找网络的边缘连通性

我想使用最大流算法（Edmond Karp / Ford-Fulkerson 算法）找到无向图的边连通性（即要删除以断开图连接的最小边数），

我知道我可以通过找到图的每两个节点之间的最小最大流量来完成此任务，但这将导致 O(|V| ^ 2) 数量的流量网络，

int Edge-Connectivity(Graph G){
    int min = infinite;
    for (Vertex u: G.V){
        for (Vertex v: G.V){
           if (u != v){ 
             //create directed graph Guv (a graph with directed edges and source u and sink v)
             //run Edmonds-Karp algorithm to find the maximum flow |f*|
             if (min > |f*|)
               min = |f*|;
           }    
         }
     }
     return min;
}

但我想用 |V| 来做到这一点流网络（仅运行最大流算法 O(|V|) 次）而不是 O(|V| ^ 2) 个

区分节点v在你的图表中。计算，对于每一个w以外v，最大流量来自v to w。自从v必须位于图的全局最小割的一侧，而其他东西必须位于另一侧，其中一个流将识别全局最小割。

郝和奥林提出了一个技巧，如果您使用预流推送算法，则全局最小割计算所需的时间与最小 (s,t) 割问题的时间差不多。它的优点是实用。 Karger 有一个随机算法，可以在 O(n polylog(n)) 时间内完成，但我不知道有任何实现，更不用说快速实现了。