Lecture 30 - 04/05

Minimum Spanning Trees

Prim's Algorithm

public PrimMST(Graph G) {
distTo = new double[G.V()];
Edge[] edgeTo = new Edge[G.V()];
boolean[] marked = new boolean[G.V()];
PQ<Double> fringe = new PQ<>(G.V());
distTo[s] = 0.0; // Arbitrary start node
setAllDistancesToInfinityExceptS(distTo);
fringe.insert(s, distTo[s]);
// Fringe ordered by distTo the cut tree
// Add vertices in order of distance from cut tree
while (!fringe.isEmpty()) {
int v = fringe.delMin();
scan(G, v);
}
}
private void scan(Graph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v)) {
int w = e.other(v); // Other vertex in edge
if (marked[w]) { continue; } // Already in MST so go to next edge
if (e.weight() < distTo[w]) { // This is a better path so update MST
distTo[w] = e.weight();
edgeTo[w] = e;
if (fringe.contains(w)) {
pq.decreasePriority(w, distTo[w]);
} else {
pq.insert(w, distTo[w]);
}
}
}

Kruskal’s Algorithm:

public KruskalMST {
private Queue<Edge> mst = new Queue<>();
public KruskalMST(Graph G) {
PQ<Double> fringe = new PQ<>(G.V());
for (Edge e : G.E()) {
fringe.insert(e);
}
// Weighted Quick Union with Path Compression (disjoint set)
WeightedQuickUnionPC uf = new WeightedQuickUnionPC(G.V());
while (!fringe.isEmpty() && mst.size() < G.V() - 1) {
Edge e = fringe.delMin();
int v = e.from();
int w = e.to();
if (!uf.connected(v, w)) {
uf.union(v, w);
mst.enqueue(e);
}
}
}
}