Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph.
//To Construct the minimum spanning tre for a graph using Prim's Algorithm
import java.io.*;
class Primal {
static int v = 0, e = 0, MAXNODE = 50, INFINITY = 10000;
static int adj[][] = new int[MAXNODE][MAXNODE];
static int visited[] = new int[MAXNODE];
static int path[] = new int[MAXNODE];
static int dist[] = new int[MAXNODE];
static void buildGraph() throws IOException {
int a, b, c, i, j;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter the number of vertices:-\t");
v = Integer.parseInt(br.readLine());
System.out.print("Enter the number of Edges :-\t");
e = Integer.parseInt(br.readLine());
System.out.println("\nFor each edge enter the source vertex,destination vertex & weight:");
for (i = 1; i <= e; i++) {
System.out.print("Source " + i + ":-\t");
a = Integer.parseInt(br.readLine());
System.out.print("Destination " + i + ":-\t");
b = Integer.parseInt(br.readLine());
System.out.print("Weight " + i + ":-\t");
c = Integer.parseInt(br.readLine());
adj[a - 1][b - 1] = adj[b - 1][a - 1] = c;
System.out.println();
}
System.out.println("\nAdjecency matrix for the given graph:-");
for (i = 0; i < v; i++) {
for (j = 0; j < v; j++)
System.out.print(adj[i][j] + "\t");
System.out.println();
}
}
static void prim(int start) throws IOException {
for (int i = 0; i < v; i++) {
visited[i] = path[i] = 0;
dist[i] = INFINITY;
}
int nv = 1, curr = start, min;
visited[curr] = 1;
while (nv != v) {
for (int j = 0; j < v; j++)
if (adj[curr][j] != 0 && visited[j] != 1)
if (dist[j] > adj[curr][j]) {
dist[j] = adj[curr][j];
path[j] = curr;
}
min = INFINITY;
for (int j = 0; j < v; j++)
if (visited[j] != 1 && dist[j] < min) {
min = dist[j];
curr = j;
}
visited[curr] = 1;
nv++;
}
int c = 0;
for (int j = 1; j < v; j++)
c += dist[j];
System.out.println("\nThe minimum cost of spanning tree is:" + c);
System.out.println("\nMinimum spanning tree is as follows: ");
for (int i = 1; i < v; i++)
System.out.println("Verex " + (i + 1) + " is connected to vertex " + (path[i] + 1));
}
public static void main(String[] args) throws IOException {
buildGraph();
prim(0);
}
}
/* OUTPUT
Enter the number of vertices:- 5
Enter the number of Edges :- 7
For each edge enter the source vertex, destination vertex & weight:
Source 1:- 1
Destination 1:- 2
Weight 1:- 2
Source 2:- 1
Destination 2:- 5
Weight 2:- 8
Source 3:- 2
Destination 3:- 3
Weight 3:- 6
Source 4:- 2
Destination 4:- 4
Weight 4:- 12
Source 5:- 2
Destination 5:- 5
Weight 5:- 7
Source 6:- 3
Destination 6:- 4
Weight 6:- 10
Source 7:- 4
Destination 7:- 5
Weight 7:- 4
Adjecency matrix for the given graph:-
0 2 0 0 8
2 0 6 12 7
0 6 0 10 0
0 12 10 0 4
8 7 0 4 0
The minimum cost of spanning tree is: 19
Minimum spanning tree is as follows:
Verex 2 is connected to vertex 1
Verex 3 is connected to vertex 2
Verex 4 is connected to vertex 5
Verex 5 is connected to vertex 2
*/