# Constructing The Minimum Spanning Tree for a Graph using Prim’s Algorithm

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;
System.out.print("Enter the number of vertices:-\t");
System.out.print("Enter the number of Edges   :-\t");
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");
System.out.print("Destination " + i + ":-\t");
System.out.print("Weight " + i + ":-\t");
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.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)
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
*/
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.