執行Kruskalls算法時對電路進行測試

Question

我正在嘗試編寫一個能夠找到最小生成樹的程序。但是我對這個算法有一個問題，就是測試電路。在java中執行此操作的最佳方法是什麼？

確定這裏是我的代碼

import java.io.*; 
import java.util.*; 

public class JungleRoads 
{ 
    public static int FindMinimumCost(ArrayList graph,int size) 
    { 
     int total = 0; 
     int [] marked = new int[size];  //keeps track over integer in the mst 

     //convert an arraylist to an array 
     List<String> wrapper = graph; 
     String[] arrayGraph = wrapper.toArray(new String[wrapper.size()]); 
     String[] temp = new String[size]; 
     HashMap visited = new HashMap(); 


     for(int i = 0; i < size; i++) 
     { 
      // System.out.println(arrayGraph[i]); 
      temp = arrayGraph[i].split(" "); 

      //loop over connections of a current node 
      for(int j = 2; j < Integer.parseInt(temp[1])*2+2; j++) 
      { 

       if(temp[j].matches("[0-9]+")) 
       { 
        System.out.println(temp[j]); 
       } 
      } 


     } 


     graph.clear(); 
     return total; 


    } 


    public static void main(String[] args) throws IOException 
    { 

     FileReader fin = new FileReader("jungle.in"); 
     BufferedReader infile = new BufferedReader(fin); 

     FileWriter fout = new FileWriter("jungle.out"); 
     BufferedWriter outfile = new BufferedWriter(fout); 


     String line; 
     line = infile.readLine(); 
     ArrayList graph = new ArrayList(); 

     do 
     { 

      int num = Integer.parseInt(line); 
      if(num!= 0) 
      { 

       int size = Integer.parseInt(line)-1; 

       for(int i=0; i < size; i++) 
       { 
        line = infile.readLine(); 
        graph.add(line); 
       } 

       outfile.write(FindMinimumCost(graph, size)); 
      } 


      line = infile.readLine(); 
     }while(!line.equals("0")); 

    } 
} 

Answer 1

Kruskall算法不會搜索週期，因爲它不是性能高效的;但是嘗試創建一個樹形組件，然後將它們連接到對方。正如你所知道的，如果你用一條新的邊連接兩棵不同的樹，你將創建新的樹並且不需要檢查週期。

如果你看一下wiki page算法如下：

1. create a forest F (a set of trees), where each vertex in the graph is a separate tree 
2. create a set S containing all the edges in the graph 
3. while S is nonempty and F is not yet spanning 
    a. remove an edge with minimum weight from S 
    b. if that edge connects two different trees, then add it to the forest, combining 
     two trees into a single tree 
    c. otherwise discard that edge. 

你應該使用Disjoint Set Data Structure這一點。再次從wiki：

首先使用比較排序在O（E日誌E） 時間按重量排序的邊緣;這允許步驟「從S中移除具有最小重量的邊緣」 以恆定時間操作。接下來，我們使用不相交集合的數據結構（Union & Find）來跟蹤哪些頂點在哪個組件中。我們需要執行O（E）操作，兩個'查找'操作 以及可能的每個邊的一個聯合。即使是一個簡單的不相交設置的數據結構，例如按級別結合的不相交集合森林，也可以在O（E log V）時間內執行O（E）操作。因此總時間爲O（E log E） = O（E log V）。

---

創建不交的森林

現在你可以看看Boost Graph Library-Incremental Components一部分。 你應該實現一些方法：MakeSet,查找,聯盟，之後，你可以實現kruskall的算法。你所做的只是處理一些集合，而最簡單的方法就是使用鏈表。

每個集合都有一個名爲的元素，它是集合中的第一個元素。

1-首先通過鏈表實現MakeSet：

這通過使每個頂點在圖中它自己的組件的 構件準備增量 連接的組件算法不相交集合的數據結構（或設置）。

function MakeSet(x) 
    x.parent := x 

2-實施查找方法：

你應該只初始化每個頂點（元素）作爲新的一組有代表性的元素，可以由家長設定他們以自己這樣做

發現包含頂點x組代表性元素：

function Find(x) 
if x.parent == x 
    return x 
else 
    return Find(x.parent) 

if部分檢查元素是否具有代表性元素。我們通過將它們作爲它們的父代來設置集合的所有代表性元素作爲其第一個元素。

3-最後，當你得到了所有以前的事情簡單的部分是實現聯盟方法：

function Union(x, y) 
xRoot := Find(x) // find representative element of first element(set) 
yRoot := Find(y) // find representative element of second element(set) 
xRoot.parent := yRoot // set representative element of first set 
         // as same as representative element of second set 

現在你應該如何運行Kruskall？

首先將所有節點放在n不相交集合中MakeSet方法。在找到所需邊（未檢查和最小邊）後的每一步中，通過查找其端點頂點的相關集。如果它們相同，則查找方法（它們的代表性元素），因爲此邊導致循環，如果它們在不同的集合中，則使用聯合方法來合併這些集合。因爲每個集合都是樹的結合。

您可以通過爲不相交集合選擇更好的數據結構來優化這一點，但現在我認爲就足夠了。如果你對更先進的數據結構感興趣，你可以實現排名基本方式，你會發現它在維基，這很容易，但我沒有提到它，以防止困惑。

Answer 2

如果頂點被標記在某種程度上，所有你需要做的是檢查是否選擇了邊緣的兩個頂點之前已訪問過這將表明一個循環。

因此，如果它用整數實現，你可以使用一個布爾數組標記哪些頂點已被選中。

boolean[] visited = new boolean[vertex-count-1]; 

或者，如果頂點被標記爲字符串，您可以將它們添加到地圖，並檢查它們是否已被添加。

Answer 3

要檢查電路，您需要使用聯合查找數據結構。最簡單的方法就是鏈接列表，但有更高效的實現。如果你想自己實現一個，這個鏈接可以幫助你。

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

或者下面是一個Java實現的鏈接：

http://www.koders.com/java/fid125D835ECD1C1C701008C456A93A7179FA06D196.aspx

基本上，工會查找數據結構允許你跟蹤不相交集合的元素，並支持兩個操作：

1) Find, which takes an element as an argument and tells you which set it is in 
2) Union, which takes 2 disjoint sets and merges them 

比方說，你將形成MST的邊緣陣列是S。這個想法是，你可以使用Union-Find來創建一個集合，C，該集合跟蹤S中邊緣連接圖的哪些頂點。當C包含圖中的所有頂點時，就完成了，並檢查邊的添加是否會創建一個循環，等於檢查它連接的兩個頂點是否已經在C中（通過使用兩個Find操作）。

所以，如果E是集圖中的所有邊緣，你的更新操作可以繼續像這樣：

Remove edge, e from E, with minimum weight (say that it connects vertices v1 and v2) 
    Find(v1) and Find(v2) 
    If v1 and v2 are both in C then continue 
    Else, Union(C,{v1,v2}) and append e to S 

你停止更新一次C包含圖形的每個頂點。

Answer 4

如果您檢查週期，使用DFS它將是非常低效的。但你可以使用Disjoint Set。連接時，您只需檢查您的節點是否在相同的連接組件中。

另外請注意，你必須檢查你的原始連接，因爲在這種情況下，Kruskall算法將找到生成樹而不是生成樹。

Answer 5

通過Tarjan的SCC（強連通組件）算法，檢測循環的功能最強大，如果不是最常用的方法。在任何情況下，這個問題已經有了答案：

Finding all cycles in a directed graph