Minimum Spanning Tree

Given an undirected, weighted graph G, a minimum spanning tree (MST) is a spanning tree of minimum total weight. A spanning tree contains all vertices in G, and enough edges to be connected without any cycles. If G has N nodes, then an MST for G will have N-1 edges.

We are going to study two algorithms for MST. Both are greedy algorithms. At each step a greedy algorithm chooses the best move available at that step.

Kruskal's Algorithm

	sort the edges in ascending order by weight
	while there are less than N-1 edges in the MST {
	   choose an edge(u,v) of lowest cost which is not in the MST
	   if ((u, v) doesn't cause a cycle in the MST
	      add (u, v) to the MST
	   else
	      discard (u, v)
	}

In Kruskals's algorithm the edges added to the MST may not form a tree (it may be not connected) until the the algorithm is complete. If there is more than one "least cost edge", choose any one. Don't worry if the new edge doesn't connect to any nodes already in the MST.

Prim's Algorithm

	pick any vertex v and add it to the MST.
	while (there are vertices not in the MST) {
	   find lowest cost edge (w, u) from a vertex w in the MST to
	   a vertex not in the MST
	   add u and the edge (w, u) to the MST
	}

If there is more than one edge that has the lowest cost, you can pick any one.

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2017