Java Reference
In-Depth Information
/
**
Computeaminimal-costspanningtree
*
/
staticvoidPrim(GraphG,ints,int[]D,int[]V){
for(inti=0;i<G.n();i++) //Initialize
D[i]=Integer.MAXVALUE;
D[s]=0;
for(inti=0;i<G.n();i++){//Processthevertices
intv=minVertex(G,D);
G.setMark(v,VISITED);
if(v!=s)AddEdgetoMST(V[v],v);
if(D[v]==Integer.MAXVALUE)return;//Unreachable
for(intw=G.first(v);w<G.n();w=G.next(v,w))
if(D[w]>G.weight(v,w)){
D[w]=G.weight(v,w);
V[w]=v;
}
}
}
Figure11.21
An implementation for Prim's algorithm.
/
**
Prims'sMSTalgorithm:priorityqueueversion
*
/
staticvoidPrim(GraphG,ints,int[]D,int[]V){
intv; //Thecurrentvertex
DijkElem[]E=newDijkElem[G.e()];//Heapforedges
E[0]=newDijkElem(s,0); //Initialvertex
MinHeap<DijkElem>H=newMinHeap<DijkElem>(E,1,G.e());
for(inti=0;i<G.n();i++) //Initialize
D[i]=Integer.MAXVALUE; // distances
D[s]=0;
for(inti=0;i<G.n();i++){ //Now,getdistances
do{v=(H.removemin()).vertex();}//Getposition
while(G.getMark(v)==VISITED);
G.setMark(v,VISITED);
if(v!=s)AddEdgetoMST(V[v],v);//AddedgetoMST
if(D[v]==Integer.MAXVALUE)return;//Unreachable
for(intw=G.first(v);w<G.n();w=G.next(v,w))
if(D[w]>G.weight(v,w)){ //UpdateD
D[w]=G.weight(v,w);
V[w]=v; //Whereitcamefrom
H.insert(newDijkElem(w,D[w]));
}
}
}
Figure11.22
An implementation of Prim's algorithm using a priority queue.
