Java Reference
In-Depth Information
/ ** HeapelementimplementationforKruskal'salgorithm * /
classKruskalElemimplementsComparable<KruskalElem>{
privateintv,w,weight;
publicKruskalElem(intinweight,intinv,intinw)
{weight=inweight;v=inv;w=inw;}
publicintv1(){returnv;}
publicintv2(){returnw;}
publicintkey(){returnweight;}
publicintcompareTo(KruskalElemthat){
if(weight<that.key())return-1;
elseif(weight==that.key())return0;
elsereturn1;
}
}
/ ** Kruskal'sMSTalgorithm * /
staticvoidKruskal(GraphG){
ParPtrTreeA=newParPtrTree(G.n());//Equivalencearray
KruskalElem[]E=newKruskalElem[G.e()];//Minheaparray
intedgecnt=0;//Countofedges
for(inti=0;i<G.n();i++) //Putedgesinthearray
for(intw=G.first(i);w<G.n();w=G.next(i,w))
E[edgecnt++]=newKruskalElem(G.weight(i,w),i,w);
MinHeap<KruskalElem>H=
newMinHeap<KruskalElem>(E,edgecnt,edgecnt);
intnumMST=G.n(); //Initiallynclasses
for(inti=0;numMST>1;i++){//Combineequivclasses
KruskalElemtemp=H.removemin();//Nextcheapest
intv=temp.v1();intu=temp.v2();
if(A.differ(v,u)){ //Ifindifferentclasses
A.UNION(v,u); //Combineequivclasses
AddEdgetoMST(v,u);//AddthisedgetoMST
numMST--; //OnelessMST
}
}
}
Figure11.25 An implementation for Kruskal's algorithm.
11.6
Further Reading
Many interesting properties of graphs can be investigated by playing with the pro-
grams in the Stanford Graphbase. This is a collection of benchmark databases and
graph processing programs. The Stanford Graphbase is documented in [Knu94].
11.7
Exercises
11.1 Prove by induction that a graph with n vertices has at most n(n1)=2 edges.
11.2 Prove the following implications regarding free trees.
Search WWH ::




Custom Search