Minimum Spanning Trees

Joshua Pan

Graph Crash Course

Graph: a set of vertices and set of edges joining different pairs of distinct vertices�Subgraph: a graph formed by a subset of vertices and edges of the original graph�Path: a sequence of vertices such that each pair of consecutive vertices are joined by an edge�Cycle: a path that starts and ends at the same vertex�Connected Graph: there is a path between any pair of distinct vertices�Tree: a connected graph with no cycles�Weighted Graph: a graph with weights assigned to �each edge

So what are (minimum) spanning trees?

Spanning tree: a subgraph that contains all vertices of the vertices of the original graph and is a tree�Minimum spanning tree: a spanning tree of a weighted graph for which the sum of all the weights of its edges is minimal

Algorithms for finding MSTs

Boruvka’s Algorithm�Prim’s (Jarnik’s) Algorithm (Jarnik 1930; Prim 1957)�Kruskal’s Algorithm�Reverse-delete Algorithm�etc…

For regular spanning trees:�simple DFS or BFS will work

Fun Fact: Stigler’s law states that no scientific discovery is named after its original discoverer.

​

Looks like Prim took all the credit. Jarnik….

​

Question: What did Prim say when he couldn’t get his algorithm to work?

General greedy algorithm for MSTs

Forest: a graph containing one or more trees�Given a connected graph G with n vertices, we construct subgraphs T₀, T₁, … T_n-1 where each T_k is a forest of n-k trees and T_n-1 is MST for G. The algorithm follows:�Step 0 (initialize): T₀ is a forest of n trees, where each tree consists of a single vertex of G. (T₀ has no edges).�Step k: Given T_k-1, select one of the trees T’ and find the minimal unused edge e_k in G coming out of T’ such that adding e_k to T_k-1 will not create a circuit. Let T_k be the union of T_k-1 and e_k.�T_n-1 will be a forest of one tree, which is clearly a spanning tree for G.

But how do you pick that one tree T’?�That is where each algorithm differs from each other.

The beauty in the tree

Boruvka’s Algorithm: At the beginning of the algorithm, enqueue all the trees in T₀. At each step select the next tree.

Prim’s Algorithm: Choose a single tree in the beginning of the algorithm and always use that tree.

Kruskal’s Algorithm: Choose the tree for which e_k would be minimal.

--------------------------------------------------�Reverse-delete Algorithm: Get rid of the largest weighted�edge, which still keeps the graph connected,�until you are left with n-1 edges.