Борувка М.С. Алгоритм

Question

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