Boruvka MST Algorithm

Question

Помогите мне с помощью алгоритма Boruvka для создания минимально-охватывающего дерева. Я написал код алгоритма, смотрящий на примере, приведенный Седжвиком, но, видимо, сделал кучу бессмыслицы, потому что алгоритм никогда не выходит из цикла. Скажите, пожалуйста, где я сделал ошибки и как их исправить, я буду очень благодарен. Код ниже. 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:. Graph Алгоритм». И вот его код:

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 (я не знаю поведение переполнения по умолчанию по умолчанию, поэтому не знаю, что на самом деле произойдет, когда оно достигнет 2^32-1). Это, вероятно, не то, что вы намереваетесь.