使用Kruskal算法尋找圖的最小切割值

我是一名初學者，我試圖用Java中的Kruskal算法找到圖的最小切割。使用Kruskal算法尋找圖的最小切割值

我已經到了我可以讀取輸入的位置，並創建vertexCount^2數量的邊緣隨機權重的MST。我所要做的就是從我的MST中找出需要多少次切割來分離S和V-S。這將允許我選擇vertexCount^2個選項中的最小值。

我想我理解正確，我應該忽略MST的最後一個邊緣來獲得S和V-S。但是我很難弄清楚有多少邊連接S和V-S。

所以我的問題是：1）是vertexCount^2隨機MST的足以確信它將包含最小切？ 2）我怎樣才能找到有多少邊連接S和V-S？

PS。這是我的代碼片段形式：

  // create weighted edge graph from input.txt 
      int vertexCount, edgeCount; 
      Edge edgeTemp; 
      vertexCount = s.nextInt(); 
      edgeCount = s.nextInt(); 
      EdgeWeightedGraph G = new EdgeWeightedGraph(vertexCount, edgeCount); 
      for (int j = 0; j < edgeCount; j++) { 
       edgeTemp = new Edge(s.nextInt(), s.nextInt(), new Random().nextInt(edgeCount)); 
       G.addEdge(edgeTemp); 
      } 

      // create kruskal's mst from graph G 
      for (int j = 0; j < vertexCount*vertexCount; j++) { 
       KruskalMST mst = new KruskalMST(G); 
       for (Edge e : mst.edges()) { 
        System.out.println(e); 
       } 
       System.out.println(NEWLINE); 
       if (j != vertexCount*vertexCount - 2) 
        G.randomizeWeight(edgeCount); 
      }

PSS。如果這是相關的，我在編寫我的代碼時查看了http://algs4.cs.princeton.edu/43mst/的代碼。

來源

2015-10-11 hollaholl

從圖中獲取MST時，我使用了Kruskal的算法。這意味着我必須使用聯合並找到方法。

每個頂點都是它自己的父節點。從圖形中獲取不同組件的聯合時，我將組合組件（包括單例）分配給一個父代。因此，當我剩下S和V-S時，每個組件的所有頂點將具有相同的父項！

因此，我回到我的EdgeWeightedGraph並迭代圖中的所有邊（而不是MST！）。當我發現一個邊的兩個頂點具有不同的父節點時，這意味着邊連接了組件S和V-S。每當我看到像這樣的邊緣時，我都會計算++。

這給了我圖中所需的切割總數！

來源

2015-10-12 11:49:44 hollaholl

使用Kruskal算法尋找圖的最小切割值

回答

相關問題