//Algoritmi za minimalno vpeto drevo
public class MinimumSpanningTree {
class PrimVertex extends VertexAdj implements HeapPosNode {
boolean visited;
boolean intree ;
PrimVertex parent;
double distance ;
int heapIndex ;
public int compareTo(Object v) {
return Double.compare(distance, ( (PrimVertex) v).distance);
}
public Comparable getKey() {
return new Double(distance) ;
}
public void setKey(Comparable k) {
distance = ((Double)k).doubleValue();
}
public int getHeapIndex() {
return heapIndex ;
}
public void setHeapIndex(int idx) {
heapIndex = idx ;
}
}
public void printPrimTree(UGraph g) {
for (PrimVertex v = (PrimVertex)g.firstVertex(); v != null; v = (PrimVertex)g.nextVertex(v))
if (v.parent != null)
System.out.println(v.value + " - " + v.distance + " - " + v.parent.value);
}
public PrimVertex primVertex() {
return new PrimVertex() ;
}
public void prim(UGraph g) {
PQDecrease q = new HeapPos() ; // urejena po distance
PrimVertex v, w ;
Edge e;
// nobeno vozlisce se ni bilo pregledano
for (PrimVertex t = (PrimVertex)g.firstVertex(); t!= null ;
t = (PrimVertex)g.nextVertex(t))
t.visited = false;
// inicializiraj prvo vozlisce in prioritetno vrsto
v = (PrimVertex)g.firstVertex();
v.visited = true;
v.parent = null;
v.intree = false;
v.distance = 0;
q.insert(v);
while ( !q.empty() ) {
v = (PrimVertex)q.deleteMin();
v.intree = true;
e = g.firstEdge(v);
while (e != null) {
w = (PrimVertex)g.adjacentPoint(e, v);
if (! w.visited) {
w.visited = true; // je v kopici
w.intree = false; // se ni v drevesu
w.parent = v; // potencialni oce
w.distance = ((Double)e.evalue).doubleValue(); // trenutna najkrajsa povezava do drevesa
q.insert(w) ;
}
else // visited
if (! w.intree && ((Double)e.evalue).doubleValue() < w.distance) {
// nasli smo krajso povezavo do drevesa
w.parent = v; // novi potencialni oce
q.decreaseKey(w, e.evalue) ; // popravi razdaljo v prioritetni vrsti
}
e = g.nextEdge(v, e) ;
} // while e
} // while not EMPTY
} // Prim
class KruskalEdge extends KEdge implements Comparable {
boolean inForest ;
public int compareTo(Object e) {
return ((Double)evalue).compareTo((Double)((KruskalEdge)e).evalue);
}
public KruskalEdge(Comparable eval, KruskalVertex v1, KruskalVertex v2) {
super(eval, v1, v2, null);
}
}
class KruskalVertex extends KVertex {
DisjointSubset subset ;
}
public KruskalVertex kruskalVertex() {
return new KruskalVertex() ;
}
public KruskalEdge kruskalEdge(Comparable eval, KruskalVertex v1, KruskalVertex v2) {
return new KruskalEdge(eval, v1, v2) ;
}
public void kruskal(KGraph g) {
KruskalVertex v1, v2 ;
DisjointSubset s1, s2 ; // dve disjunktni podmnozici-poddrevesi
// inicializacija disjunktnih mnozic vozlisc
DisjointSet dSet = new DisjointSetForest() ; // ena mnozica je vpeto drevo
for (KruskalVertex t = (KruskalVertex)g.firstVertex(); t!= null ;
t = (KruskalVertex) g.nextVertex(t))
t.subset = dSet.makeset(t) ;
// inicializacija prioritetne vrste povezav
PriorityQueue q = new Heap() ; // urejena po length
KruskalEdge e ;
for (e = (KruskalEdge)g.firstEdge(); e!= null ; e = (KruskalEdge)g.nextEdge(e)) {
q.insert(e) ;
e.inForest = false;
}
// zgradi minimalni vpeti gozd - ce je graf povezan, zgradi minimalno vpeto drevo
while (!q.empty()) {
e = (KruskalEdge) q.deleteMin();
v1 = (KruskalVertex)g.endPoint1(e) ;
v2 = (KruskalVertex)g.endPoint2(e) ;
// doloci poddrevesi obeh vozlisc
s1 = dSet.find(v1.subset);
s2 = dSet.find(v2.subset);
if (s1 != s2) {
// e je povezava med dvemi razlicnimi vpetimi drevesi
dSet.union(s1, s2) ;
e.inForest = true;
}
} // while
} // Kruskal
public void printKruskalTree(KGraph g) {
for (KruskalEdge e = (KruskalEdge)g.firstEdge(); e != null; e = (KruskalEdge)g.nextEdge(e))
if (e.inForest)
System.out.println(g.endPoint1(e).value + " - " + e.evalue + " - " + g.endPoint2(e).value);
}
public static void main(String[] args) {
MinimumSpanningTree mst = new MinimumSpanningTree();
// first Prim, then Kruskal
UGraph g = new UGraphAdj() ;
// primer: mrezni diagram s slike 54
PrimVertex va[] = new PrimVertex[7] ;
for (int i = 0 ; i < va.length ; i++) {
va[i] = mst.primVertex();
va[i].value = new String(Integer.toString(i)) ;
g.insertVertex(va[i]);
}
g.insertEdge(va[0],va[1]);
g.firstEdge(va[0]).evalue = new Double(11) ;
g.firstEdge(va[1]).evalue = new Double(11) ;
g.insertEdge(va[0],va[2]);
g.firstEdge(va[0]).evalue = new Double(17) ;
g.firstEdge(va[2]).evalue = new Double(17) ;
g.insertEdge(va[0],va[3]);
g.firstEdge(va[0]).evalue = new Double(27) ;
g.firstEdge(va[3]).evalue = new Double(27) ;
g.insertEdge(va[1],va[2]);
g.firstEdge(va[1]).evalue = new Double(15) ;
g.firstEdge(va[2]).evalue = new Double(15) ;
g.insertEdge(va[1],va[3]);
g.firstEdge(va[1]).evalue = new Double(9) ;
g.firstEdge(va[3]).evalue = new Double(9) ;
g.insertEdge(va[2],va[3]);
g.firstEdge(va[2]).evalue = new Double(13) ;
g.firstEdge(va[3]).evalue = new Double(13) ;
g.insertEdge(va[2],va[4]);
g.firstEdge(va[2]).evalue = new Double(38) ;
g.firstEdge(va[4]).evalue = new Double(38) ;
g.insertEdge(va[3],va[5]);
g.firstEdge(va[3]).evalue = new Double(16) ;
g.firstEdge(va[5]).evalue = new Double(16) ;
g.insertEdge(va[3],va[6]);
g.firstEdge(va[3]).evalue = new Double(3) ;
g.firstEdge(va[6]).evalue = new Double(3) ;
g.insertEdge(va[4],va[5]);
g.firstEdge(va[4]).evalue = new Double(7) ;
g.firstEdge(va[5]).evalue = new Double(7) ;
g.insertEdge(va[6],va[5]);
g.firstEdge(va[6]).evalue = new Double(34) ;
g.firstEdge(va[5]).evalue = new Double(34) ;
System.out.println("Graph:") ;
g.printGraph();
System.out.println("Prim's minimum spanning tree:") ;
mst.prim(g) ;
mst.printPrimTree(g) ;
KGraph k = new KGraphList() ;
KruskalVertex vk[] = new KruskalVertex[7] ;
for (int i = 0 ; i < vk.length ; i++) {
vk[i] = mst.kruskalVertex();
vk[i].value = new String(Integer.toString(i)) ;
k.insertVertex(vk[i]);
}
KruskalEdge e ;
e = mst.kruskalEdge(new Double(11), vk[0], vk[1]) ;
k.insertEdge(e);
e = mst.kruskalEdge(new Double(17), vk[0], vk[2]) ;
k.insertEdge(e);
e = mst.kruskalEdge(new Double(27), vk[0], vk[3]) ;
k.insertEdge(e);
e = mst.kruskalEdge(new Double(15), vk[1], vk[2]) ;
k.insertEdge(e);
e = mst.kruskalEdge(new Double(9), vk[1], vk[3]) ;
k.insertEdge(e);
e = mst.kruskalEdge(new Double(13), vk[2], vk[3]) ;
k.insertEdge(e);
e = mst.kruskalEdge(new Double(38), vk[2], vk[4]) ;
k.insertEdge(e);
e = mst.kruskalEdge(new Double(16), vk[3], vk[5]) ;
k.insertEdge(e);
e = mst.kruskalEdge(new Double(3), vk[3], vk[6]) ;
k.insertEdge(e);
e = mst.kruskalEdge(new Double(7), vk[4], vk[5]) ;
k.insertEdge(e);
e = mst.kruskalEdge(new Double(34), vk[5], vk[6]) ;
k.insertEdge(e);
System.out.println("Graph:") ;
k.printGraph();
System.out.println("Kruskal's minimum spanning tree:") ;
mst.kruskal(k) ;
mst.printKruskalTree(k) ;
}
}
