MST Burke Algorithm

Question

Help me with the Boruvka algorithm to create a minimally spanning tree. I wrote an algorithm code that looks at an example given by Sedgwick, but apparently made a bunch of nonsense because the algorithm never goes out of the loop. Please tell me where I made mistakes and how to fix them, I will be very grateful. The code is below. PS. sorry for my English:)

public class Boruvka
{
    private Edge[] mst;
    /**
     * Edges not yet discarded and not yet in the MST
     */
    private Edge[] wannabes;
    /**
     * Each component 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 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;
    }
}

I wrote this code looking at the code given by Sedgwick in his "Algorithms in java. Part 5: Graph Algorithm". And here is his code:

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]; }
      }
  }
}

Please help me find the differences between him and mine and correct them. PS. I'm sorry about my english.

Answer 1

Here begins.

Consider a loop forwith this control statement:

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). , , , .