CS61B: Lecture 25

Minimum Spanning Trees

• Warm up: Given an undirected graph, how do we determine if it contains any cycles?
  • We use DFS from any source vertex and keep going until we see a marked node. Since we already visited that node, there must be a cycle.
  • We can also use a Weighted-QuickFind Union. Add all edges, if two edges are already connected, then there must be a cycle.
• Given an undirected graph, a spanning tree T is a subgraph of G, where T:
  • Is connected.
  • Is acyclic.
  • Includes all of the vertices.
    • Basically just a tree that includes all vertices.
• A minimum spanning tree is a spanning tree of minimum total weight
  • Ex: network of power lines that connect a bunch of buildings.
• Minimum spanning trees could be used for handwriting recognition and also image processing.

The Cut Property

• A cut is an assignment of a graph’s nodes to two non-empty sets.

  • Roughly there are $2^

    V

    $ cuts.

• A crossing edge is an edge which connects a node from one set to a node from the other set.
• The Cut Property: Given any cut, minimum weight crossing edge is in the MST.
  • A crossing edge is an edge that connects both cuts.

Proof of the Cut Property

• Let X be the MST. SUppose that the minimum crossing edge e is not in X.
  • Adding e to X creates a cycle.
  • Some other edge f in X must also be a crossing edge and be part of the cycle.
    • This is because all cycles are connected by the tree. At least one crossing edge must exist in our MST.
  • Removing f and adding e is a lower weight spanning tree.
  • This gives us a contradiction.

Generic MST Finding Algoritum

• We take advantage of the Cut Property.
  • Start with no edges in the MST.
    • Find a cut that has no crossing edges in the MST.
    • Add the smallest crossing edge to the MST.
    • Repeat until V-1 edges.

Prims Algorithm

• Start from some arbitrary start node
  • Repeatedly add the shortest edge that has one node inside the MST under construction.
    • The MST that we are forming versus the rest of the graph forms two separate cuts. We always add the edge with the smallest weight connecting the two cuts.
    • Basically just Djikstra’s algorithm but PQ is based on edge length and not the total distance from the root node.
• For Prims, we insert all vertices into the fringe PQ, and store all vertices in order of the distance from the tree.
  • All vertices begin as infinitely far away. Source node has distance of zero. The fringe distances are updated based on the vertice’s closest distance to some node in our MST under construction.
  • Every time we pop off an edge from our fringe, we update the fringe distances (distance from vertex to tree) of all the vertices remaining. We update the distance of all vertices on the fringe adjacent to the edge we just relaxed.
• Prims and Dijkstra’s algorithms are exactly the same, except Dijkstra consideres the “distance from the source”, and Prim’s considers the “distance from the tree.”
  • Relaxation in Dijkstra’s considers an edge better based on distance to source.
  • Relaxation in Prims’s considers an edge better based on distance to tree.

public class PrimMST {
	public PrimMST(EdgeWeightedGraph G) {
		edgeTo = new Edge[G.V()];
		distTo = new double[G.V()];
		marked = new boolean[G.V()];
		fringe = new SpecialPQ<Double>(G.V());
	
		distTo[s] = 0.0;
		setDistancesToInfinityExceptS(s);
		insertAllVertices(fringe);
	
		/* Get vertices in order of distance from tree. */
		while (!fringe.isEmpty()) {
			int v = fringe.delMin();
			scan(G, v);
		} 
	}

  	private void scan(EdgeWeightedGraph G, int v) {
		marked[v] = true;
		for (Edge e : G.adj(v)) {
			int w = e.other(v);
			if (marked[w]) { continue; } 
			if (e.weight() < distTo[w]) {
			distTo[w] = e.weight();
			edgeTo[w] = e;
			pq.decreasePriority(w, distTo[w]);
			}
		}
	}
}

Kruskal’s Algorithm

• Consider the edges in order of increasing weight, and add to MST unless a cycle is created.
  • Repeat until V-1 edges. By that point, our graph is connected.
• To Check if there is a cycle, we must run DFS.
  • However, a weightedQuickUnion is also a valid way of checking for cycles.
  • Every time we consider an edge that we want to add, we check if they are already connected in the WQU.
    • If they are connected, then we skip over the edge.
    • If they are not connected, then we add the connection to WQU and add the edge to our MST.