Boruvka MST算法

Question

請幫我用Boruvka算法創建最小生成樹。我用Sedgwick給出的例子編寫了一個算法的代碼，但顯然做了一堆廢話，因爲算法永遠不會退出循環。請告訴我，我犯了什麼錯誤以及如何解決它們，我會非常感激。下面的代碼。 PS。對不起，我的英語:)

public class Boruvka 
{ 
    private Edge[] mst; 
    /** 
    * Edges not yet discarded and not yet in the MST 
    */ 
    private Edge[] wannabes; 
    /** 
    * Each component's nearest neighbor with find component numbers as indices 
    */ 
    private Edge[] neighbors; 
    /** 
    * Graph representation on which we are searching for MST 
    */ 
    private Graph g; 
    /** 
    * 
    */ 
    private UnionFind uf; 
    // constructors and methods 
    /** 
    * constructor 
    * @param G Graph 
    */ 
    public Boruvka(Graph G) { 
     this.g = G; 
    } 
    /** 
    * Boruvka's algorithm 
    * 
    * 
    * @return minimal spanning tree - edges that form it 
    */ 

    public Edge[] BoruvkaMSTalg() 
    { 
     Edge hlpEdge = new Edge(g.getMaxWeight(), 0, 0); 
     this.uf = new UnionFind(g.getCountVerteces()); 
     this.wannabes = new Edge[this.g.getCountEdges()]; 

     /** 
     * Get all edges from the graph G to the array edges 
     */ 
     for (int i=0; i < g.getCountEdges(); i++) 
      this.wannabes[i] = g.getEdgeAt(i); 


     this.neighbors = new Edge[this.g.getCountVerteces()]; 
     this.mst = new Edge[this.g.getCountVerteces()+1]; 

     /** 
     * index, used to store those edges being saved for the next phase 
     */ 
     int nxtPhase; 
     int k=1; 

     for (int i=this.g.getCountEdges(); i!=0; i=nxtPhase) 
     { 
      int l, m, n; 

      for (int o=0; o<this.g.getCountVerteces(); o++) 
       this.neighbors[o] = hlpEdge; 

      for (n=0, nxtPhase=0; n<i; n++) { 
       Edge e = this.wannabes[n]; 
       l = this.uf.find(e.getSVIndex()-1); 
       m = this.uf.find(e.getDVIndex()-1); 

       if (l==m) 
        continue; 
       if (e.getWeight() < this.neighbors[l].getWeight()) 
        this.neighbors[l] = e; 
       if (e.getWeight() < this.neighbors[m].getWeight()) 
        this.neighbors[m] = e; 

       this.wannabes[nxtPhase++] = e; 
      } 

      for (n=0; n<this.g.getCountVerteces(); n++) 
       if (this.neighbors[n] != hlpEdge) { 
        l = this.neighbors[n].getSVIndex(); 
        m = this.neighbors[n].getDVIndex(); 

        if (!this.uf.find(l,m)) { 
         this.uf.unite(l,m); 
         this.mst[k++] = this.neighbors[n]; 
        } 
       } 
     } 
     System.out.println("MST by Boruvka successful"); 
     return this.mst; 
    } 
} 

我寫了這個代碼在看「Java 5中部分算法：圖形算法」在他的塞奇威克定的代碼。這裏是他的代碼：

class GraphMST 
{ private UF uf; 
    private Edge[] a, b, mst; 
    GraphMST(Graph G) 
    { Edge z = new Edge(0, 0, maxWT); 
    uf = new UF(G.V()); 
    a = GraphUtilities.edges(G); 
    b = new Edge[G.V()]; mst = new Edge[G.V()+1]; 
    int N, k = 1; 
    for (int E = G.E(); E != 0; E = N) 
     { int h, i, j; 
     for (int t = 0; t < G.V(); t++) b[t] = z; 
     for (h = 0, N = 0; h < E; h++) 
      { Edge e = a[h]; 
      i = uf.find(e.v()); j = uf.find(e.w()); 
      if (i == j) continue; 
      if (e.wt() < b[i].wt()) b[i] = e; 
      if (e.wt() < b[j].wt()) b[j] = e; 
      a[N++] = e; 
      } 
     for (h = 0; h < G.V(); h++) 
     if (b[h] != z) 
      if (!uf.find(i = b[h].v(), j = b[h].w())) 
      { uf.unite(i, j); mst[k++] = b[h]; } 
     } 
    } 
} 

請幫我找出它和我的差異，並解決它們。 PS。我很抱歉我的英語。

Answer 1

這是一個開始。

考慮for環路與此控件聲明：

for (int i=this.g.getCountEdges(); i!=0; i=nxtPhase) 

了這個循環的唯一方法是i是0。這i得到改變的地方是由環推進聲明

i = nxtPhase 

是nxtPhase得到改變的地方是這裏

this.wannabes[nxtPhase++] = e; 

所以書面，跳出循環的唯一途徑是nxtPhase去經歷所有可能的int值（我不知道Java的默認溢出行爲，所以不知道當它到達2^32-1時會發生什麼）。這可能不是你想要的。