通過使用最大流量算法

Question

查找網絡的邊緣連接我想找到邊緣連接（即邊緣的最小數量，以除去斷開的曲線圖），使用最大流量算法（愛德蒙卡普/福特 - 富爾克森算法的無向圖的），

我知道我可以通過找到的曲線圖的每一個的兩個節點之間的最小的最大流量完成這個任務，但是這將導致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）

Answer 1

區分圖中的節點v。計算除v以外的每個w，最大流量從v到w。由於v必須位於圖的全局最小切割的一側，而另一側必須有另一側，其中一個流將識別全局最小切割。

由於Hao和Orlin有一個技巧，如果使用預流推送算法，全局最小切割計算所花費的時間與最小（s，t）切割問題相同。它具有實用性的好處。 Karger有一個隨機算法，它在O（n polylog（n））時間內完成它，但我不知道有任何實現，更不用說快速實現了。