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时会发生什么）。这可能不是你想要的。