2014-02-24 53 views
0

嘗試在Java中自己編寫代碼...我創建了GraphNode類來表示具有指向其父代的節點的節點。如何將每個集合存儲在不相交集的森林中?

我還創建了一個DisjointSet類,它包含一個MakeSet方法,該方法創建GraphNode對象並使其父引用引用自身。

現在的問題是:我如何存儲每個節點,以便稍後在Union和FindSet中輕鬆訪問它?我首先想到它將它存儲在BST中,但我必須創建一個自定義TreeNode類,該類不僅存儲該值,還存儲對GraphNode的引用。有更容易的方法嗎?

回答

8

絕對有一種更簡單的方法:忘掉所有的節點業務。節點只是概念上的,不需要從字面上實現它們,而且更容易。

所有你需要的是兩個整數數組。一個存儲父母和一個存儲隊伍的人。所以在一種僞代碼中,它看起來像這樣:

disjoint_set { 
    int[] parent, rank; 
    makeset(int n) 
    { 
     rank = new int[n]; 
     parent = new int[n]; 
     for(int i = 0; i < n; i++) 
      parent[i] = i; 
    } 

    int find(int i) 
    { 
     if (parent[i] != i) 
      parent[i] = find(parent[i]); 
     return parent[i]; 
    } 

    void union(int x, int y) 
    { 
     x_root = find(x); 
     y_root = find(y); 
     if (x_root != y_root) { 
      if (rank[x_root] < rank[y_root]) 
       parent[x_root] = y_root; 
      else if (rank[x_root] > rank[y_root]) 
       parent[y_root] = x_root; 
      else { 
       parent[y_root] = x_root; 
       rank[x_root]++; 
      } 
     } 
    } 
}