Java Programming

Graph Theory Project:
1. Implement Prim's algorithm in Java using the data structures and the
pseudo-code from handout. Your output should produce a set of vertices and
edges of a spanning tree of the example.


Prim's Algorithm
Problem: Determine a minimum spanning tree.
Inputs: integer n>=2, and a connected, weighted, undirected graph containing
n vertices. The graph is represented by a two-dimensional array W, which has
both its row and columns indexed from 1 to n, where W[ i ] [ j ] is the
weight on the edge between the ith and the jth vertex.

Output: set of edges F in a minimum spanning tree for the graph.

public static set_of_edges prim( int n, number [ ] [ ] W)
{
index i, vnear;
number min;
edge e;
set_of_edges F;
index [ ] nearest = new index [2 . . n];
number [ ] distance = new number [2 . . n];

F = null or empty value;
for ( i = 2; i <= n; i++) {
nearest [ i ] = 1; // For all vertices, initialize v1 to be the nearest
distance [ i ] = W[1] [ i ]; // vertex in Y and initialize the distance
//from Y to be
} //the weight on the edge to v1.

repeat (n - 1 times) { //Add all n-1 vertices to Y.
min = (infinity)
for (i = 2; i <= n; i++); //Check each vertex for
if (0 <= distance [ i ] < min) { //being nearest to Y.
min = distance [ i ];
vnear = i;
}
e = edge connecting vertices indexed
by vnear and nearest [vnear];
add e to F;
distance[vnear] = -1; //Add vertex indexed by vnear
for ( i = 2; i <= n; i++) // to Y.
if (W[ i ] [vnear] < distance[ i ]) //For each vertex not in Y,
distance [ i ] = W[ i ] [vnear]; //update its distance from Y.
nearest[ i ] = vnear;
}
}
return F;
}