7b SPANNING TREE
IMPLEMENTATION(PRIM’S)
AIM:
To write a java program
to implement Spanning tree implementation using Prim’s algorithm.
ALGORITHM:
1. Create
a set mstSet that keeps track of vertices already included in MST.
2. Assign a key value to all vertices in the
input graph. Initialize all key values as INFINITE.
Assign key value as 0 for the first vertex so that it is
picked first.
3. While
mstSet doesn’t include all vertices
3.1. Pick a vertex u which is not there in mstSet and
has minimum key value.
3.2. Include u to
mstSet.
3.3. Update key value
of all adjacent vertices of u. To update the key values, iterate through
all adjacent vertices. For every adjacent vertex v, if weight of edge u-v
is less than the previous key value of v, update the key value as weight
of u-v.
PROGRAM :
import
java.util.InputMismatchException;
import
java.util.Scanner;
public class Prims
{
private boolean
unsettled[];
private boolean
settled[];
private int
numberofvertices;
private int
adjacencyMatrix[][];
private int key[];
public static final
int INFINITE = 999;
private int
parent[];
public Prims(int
numberofvertices)
{
this.numberofvertices
= numberofvertices;
unsettled = new boolean[numberofvertices
+ 1];
settled = new
boolean[numberofvertices + 1];
adjacencyMatrix =
new int[numberofvertices + 1][numberofvertices + 1];
key = new
int[numberofvertices + 1];
parent = new
int[numberofvertices + 1];
}
public int
getUnsettledCount(boolean unsettled[])
{
int count = 0;
for (int index = 0;
index < unsettled.length; index++)
{
if
(unsettled[index])
{
count++;
}
}
return count;
}
public void
primsAlgorithm(int adjacencyMatrix[][])
{
int
evaluationVertex;
for (int source = 1;
source <= numberofvertices; source++)
{
for (int destination
= 1; destination <= numberofvertices; destination++)
{
this.adjacencyMatrix[source][destination]
= adjacencyMatrix[source][destination];
}
}
for (int index = 1;
index <= numberofvertices; index++)
{
key[index] =
INFINITE;
}
key[1] = 0;
unsettled[1] = true;
parent[1] = 1;
while
(getUnsettledCount(unsettled) != 0)
{
evaluationVertex =
getMimumKeyVertexFromUnsettled(unsettled);
unsettled[evaluationVertex]
= false;
settled[evaluationVertex]
= true;
evaluateNeighbours(evaluationVertex);
}
}
private int
getMimumKeyVertexFromUnsettled(boolean[] unsettled2)
{
int min =
Integer.MAX_VALUE;
int node = 0;
for (int vertex = 1;
vertex <= numberofvertices; vertex++)
{
if
(unsettled[vertex] == true && key[vertex] < min)
{
node = vertex;
min = key[vertex];
}
}
return node;
}
public void
evaluateNeighbours(int evaluationVertex)
{
for (int
destinationvertex = 1; destinationvertex <= numberofvertices;
destinationvertex++)
{
if
(settled[destinationvertex] == false)
{
if (adjacencyMatrix[evaluationVertex][destinationvertex]
!= INFINITE)
{
if
(adjacencyMatrix[evaluationVertex][destinationvertex] <
key[destinationvertex])
{
key[destinationvertex]
= adjacencyMatrix[evaluationVertex][destinationvertex];
parent[destinationvertex]
= evaluationVertex;
}
unsettled[destinationvertex]
= true;
}
}
}
}
public void
printMST()
{
System.out.println("SOURCE : DESTINATION = WEIGHT");
for (int vertex = 2;
vertex <= numberofvertices; vertex++)
{
System.out.println(parent[vertex]
+ "\t:\t" + vertex +"\t=\t"+
adjacencyMatrix[parent[vertex]][vertex]);
}
}
public static void
main(String... arg)
{
int
adjacency_matrix[][];
int
number_of_vertices;
Scanner scan = new
Scanner(System.in);
try
{
System.out.println("Enter
the number of vertices");
number_of_vertices =
scan.nextInt();
adjacency_matrix =
new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Enter
the Weighted Matrix for the graph");
for (int i = 1; i
<= number_of_vertices; i++)
{
for (int j = 1; j
<= number_of_vertices; j++)
{
adjacency_matrix[i][j]
= scan.nextInt();
if (i == j)
{
adjacency_matrix[i][j]
= 0;
continue;
}
if
(adjacency_matrix[i][j] == 0)
{
adjacency_matrix[i][j]
= INFINITE;
}
}
}
Prims prims = new
Prims(number_of_vertices);
prims.primsAlgorithm(adjacency_matrix);
prims.printMST();
} catch
(InputMismatchException inputMismatch)
{
System.out.println("Wrong
Input Format");
}
scan.close();
}
}