在預流推送網絡流算法中找到一組MinCut邊緣

我有一個預流推送網絡流算法的實現，它返回流網絡的最大流量。我需要的是確定圖形中形成切割的一組飽和邊。在預流推送網絡流算法中找到一組MinCut邊緣

在我當前的實現中，我查找圖中空邊向後的飽和前緣，其中邊緣源到邊緣目標的距離大於或等於1（即，源具有更高的高度比目標）。如果圖中只有一個可能的邊集滿足最小切割，則該算法可以正常工作，但是如果算法可以在圖中找到多個切割，那麼它會返回圖中所有飽和邊。我在下面複製了我的代碼。任何幫助，高度讚賞。

public Set<Edge> cutEdges(){ 
    for (String v_name : vertices.keySet()){ 
     int v_id = vertices.get(v_name); 
     ArrayList<Edge> veList = residual_edges.get(v_id); 
     for (Edge ve : veList){ 
      boolean reverseFound = false; 
      EdgeData vinfo = (EdgeData) ve.getData(); 
      if (vinfo.getAvailable() == 0){ 
       Vertex temp1 = ve.getFirstEndpoint(); 
       Vertex temp2 = ve.getSecondEndpoint(); 
       int u_id = (v_id != vertices.get(temp1.getName().toString()) ? 
         vertices.get(temp2.getName().toString()) : vertices.get(temp1.getName().toString())); 
       ArrayList<Edge> ueList = residual_edges.get(u_id); 
       for (Edge ue : ueList){ 
        EdgeData uinfo = (EdgeData) ue.getData(); 
        if (ue.getFirstEndpoint().getName().toString().equals(temp2.getName().toString()) && 
          ue.getSecondEndpoint().getName().toString().equals(temp1.getName().toString())){        
         if (((VertexData)ue.getFirstEndpoint().getData()).getPreflowHeight() - 
           ((VertexData)ue.getSecondEndpoint().getData()).getPreflowHeight() >= 1){ 
          if (uinfo.getFlow() == 0) 
          continue; 
         } 
         reverseFound = true; 
         break; 
        } 
       } 
       if (!reverseFound){ 
        if (((VertexData)temp1.getData()).getPreflowHeight() - 
          ((VertexData)temp2.getData()).getPreflowHeight() >= 1) 
         cut_edges.add(ve); 
       } 
      } 
     } 
    } 
    return cut_edges; 
}

來源

2011-11-11 nemo

可能的重複[如何找到使用最大流算法的圖上的最小剪切？]（http://stackoverflow.com/questions/4482986/how-can-i-find-the-minimum -cut-ON-A-圖的使用-A-最大流算法） – fedorqui

我會從問題How can I find the minimum cut on a graph using a maximum flow algorithm?複製我的答案是：

從源頂點，做沿着仍然有剩餘能力（即，非飽和邊邊緣的深度優先搜索）。該切割包括「看到」（即，入射在訪問頂點處）的所有邊緣的，但是由於它們飽和，所以未被遍歷。當您注意到時，可能會有其他飽和邊緣，而不是最小切割的一部分。

來源

2011-12-10 15:05:58

在預流推送網絡流算法中找到一組MinCut邊緣

回答

相關問題