TOC PREV NEXT

Program — Minimum spanning tree

Goals

This programming assignment will give you practice working with graphs with edge weights, implementing one of the standard algorithms for graphs.

Related quizzes

Graph representations.

Readings

Weiss (either edition), sections 14.1 through 14.3, and 14.5. The shortest path and topological sorting algorithms are not directly relevant to this assignment, but they serve as useful examples of graph processing and their auxiliary data structures are similar to those you will use for your own implementation.

Problem

Do the exercise described below.

Background

A spanning tree for an undirected graph G is a tree formed by edges in G that together connect all of G's vertices. Examples appear below. A typical graph has many spanning trees.




a graph
some spanning trees

Many graph applications involve weights or costs on the edges. For example, vertices might represent cities, with an edge connecting two cities having weight equal to the distance or driving time between the cities. For such graphs, we may consider a minimum spanning tree, namely the spanning tree in which the sum of the edge weights is as small as possible. (There may be more than one minimum spanning tree, for example when the edge weights are all equal.)

Here is pseudocode for an algorithm (known as Prim's algorithm) for constructing a minimum spanning tree. 

	initialize the tree to some vertex of G;
	initialize the set Q of vertices not yet in the tree to the vertices of G;
	while (Q isn't empty) {
		pick the lightest edge that connects a vertex in the tree to a vertex v in Q
		(note that there might be two or more such edges—if more, just pick one),
		remove v from Q, and add the edge and v to the tree.

An example run follows, using the graph below. Vertex numbers appear in the circles; edge weights appear next to the edges. We arbitrarily start with the top vertex. The dark edges indicate the tree that gets constructed.
  1. Add vertex v2 and edge (v1,v2) to the tree.
  2. Vertices v3 and v4 are candidates for adding to the tree. Arbitrarily choose v3 and add it and edge (v2,v3) to the tree.
  3. Now v4 and v6 are candidates. Choose v4, and add it and edge (v2,v4) to the tree.
  4. Add v6 and either edge (v3,v6) or (v4,v6)—we arbitrarily choose the latter—to the tree.
  5. Add v5 and edge (v6,v5) to the tree.


Exercise

Implement Prim's algorithm. Your implementation should run in time O(e log n), where n is the number of vertices and e the number of edges in the graph. Be prepared to verify its running time for a tutor, with a defense of your choices for the graph representation and auxiliary data structures. Provide six tests using the graph just described, each with a different choice of starting vertex.

Code from the Weiss textbook is provided online, currently at http://www.cs.fiu.edu/~weiss/dsj3/code/code.html. (If you're using Weiss's second edition, substitute "dsj2" for "dsj3" in the above URL.)

Checklist

TOC PREV NEXT