Boruvka MST Algorithm

Question

Aidez-moi s'il vous plaît avec l'algorithme Boruvka pour créer un arbre minnimum-spanning. J'ai écrit le code d'un algorithme à la recherche d'un exemple donné par Sedgwick mais apparemment, j'avais fait un tas de bêtises, car l'algorithme ne sort jamais de la boucle. Dites-moi s'il vous plaît où j'ai fait des erreurs et comment les réparer, je serai très reconnaissant. Code ci-dessous. PS. désolé pour mon anglais :)

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

J'ai écrit ce code regardant le code donné par Sedgwick dans ses « algorithmes en Java Partie 5:. Graphique Algorithm ». Et voici son 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]; } 
     } 
    } 
} 

Aidez-moi s'il vous plaît pour trouver des différences entre elle et le mien et pour les réparer. PS. Je suis désolé pour mon anglais.

Answer 1

Voici un début.

Tenir compte de la boucle for avec cette déclaration de contrôle:

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

Le seul moyen de sortir de cette boucle est pour i d'être 0. Le seul endroit que i se change est par l'instruction avancement boucle

i = nxtPhase 

Le seul endroit que nxtPhase se change est ici

this.wannabes[nxtPhase++] = e; 

Ainsi, comme il est écrit, la seule sortie de la boucle est pour nxtPhase pour passer par toutes les valeurs possibles int (je ne connais pas le comportement de débordement par défaut de Java, donc je ne sais pas ce qui se passera réellement quand il arrivera à 2^32-1). Ce n'est probablement pas ce que vous avez l'intention de faire.