Boruvka MST Algorithm
Help me please with Boruvka algorithm for creating a minnimum-spanning tree. I wrote code of an algorithm looking on example given by Sedgwick but apparently had done a bunch of nonsense, because the algorithm never goes out of the loop. Tell me please where I have done mistakes and how to fix them, I'll be very grateful. Code 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'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开发者_如何学JAVA++] = this.neighbors[n];
}
}
}
System.out.println("MST by Boruvka successful");
return this.mst;
}
}
I wrote this code looking at 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]; }
}
}
}
Help me please to find differences between it's and mine and to fix them. PS. i'm sorry for my english.
Here's a start.
Consider the for
loop with this control statement:
for (int i=this.g.getCountEdges(); i!=0; i=nxtPhase)
The only way out of this loop is for i
to be 0
. The only place that i
gets changed is by the loop advancing statement
i = nxtPhase
The only place that nxtPhase
gets changed is here
this.wannabes[nxtPhase++] = e;
So as written, the only way out of the loop is for nxtPhase
to go through all possible int
values (I don't know the default overflow behaviour of Java so don't know what will actually happen when it gets to 2^32-1
). This is probably not what you intend.
精彩评论