CSC 245 Laboratory Exercise 6 - Minimum Spanning Tree
In this exercise you will implement Prim's Algorithm for finding a Minimum Spanning Tree (MST) embedded in a weighted graph.
Preparation - The graph shown below is called a weighted graph because its edges have values or weights assigned to them. The Minimum Spanning Tree (MST) problem is to find a tree that is made up of all the nodes in the graph and a subset of the edges such that the sum of the edge weights is a minimum.
Prim's Algorithm is an efficient method for finding the minimum spanning tree in a weighted graph. This algorithm is stated formally as follows:
Given a weighted graph G consisting of a set of vertices V and a set of edges E with weights wi,j, where,
Implementation - To implement an algorithm for the minimum spanning tree problem we need a data-representation for weighted graphs. To solve the problem manually, we can look at a picture of the graph, but for computer analysis an edge list or adjacency matrix representation is preferred. As shown in the figure above the weight of each edge is included as a parameter in the edge list and the weight replaces the boolean value in an adjacency matrix. The MST problem can be implemented using either of these data structures.
Prepare a vertex list VP and an edge list EP (that are initially empty) to hold the vertices and edges selected by Prim's Algorithm.
- Choose an any starting vertex vi and place it in the vertex list VP.
- Find the smallest weight edge ei,jincident with a vertex in the vertex list whose inclusion in the edge list will not create a cycle. This can be done by verifying that the other vertex vj is not already in the vertex list.
- Include this edge in the edge list EP and the associated vertex vj in the vertex list VP.
- Repeat Steps 2 and 3 until all vertices of the graph are in the vertex list VP.
The solution to the MST is the edge list and the sum of the weights of the edges in the edge list EP is the minimum weight (sometimes we say minimal since there may be more than one minimum) spanning tree.
The type of graph traversal being performed in Prim's Algorithm is neither purely depth-first or breadth-first since the only edges that are examined are those incident with vertices in the selected vertex list. A simple way to implement Steps 2 and 3 is in a loop as shown in the pseudo-code below:
wmin=some_large_value
For every edge ek=(vi,vj,wij) in E
if [(vi in VP and vj not in VP) or (vi not in VP and vj in VP)] and wijwmin then
wmin = wij
emin=ek
end if
end loop
Include emin in EP and viand vj in VP.
This is repeated until every vertex in V is included in VP.
Analysis - Test your algorithm on the graph shown in the figure above. Verify that the edge list in EP represents a Minimum Spanning Tree of this graph. Submit source code, input data file and an example output from your program.