The Minimum Spanning Tree (MST) problem is a fundamental topic in graph theory and algorithms. In this blog post, we demonstrate how to implement Prim’s Algorithm in Java to construct a minimum spanning tree for a given graph.
What is a Minimum Spanning Tree?
A spanning tree of a graph is a subgraph that includes all the vertices of the original graph connected by the minimum number of edges without forming any cycles. A minimum spanning tree is the one with the least total edge weight.
How Prim’s Algorithm Works?
Prim’s algorithm is a greedy algorithm that always chooses the smallest edge connecting a node in the MST to a node outside of it. Here’s how it works:
- Start from any vertex: Begin with any arbitrary vertex. This becomes part of the MST.
- Mark it as visited: Track which vertices are already included in the MST.
- Choose the smallest edge: From the visited nodes, pick the edge with the minimum weight that leads to an unvisited node.
- Add the new node and edge to MST: Include this new edge and the corresponding unvisited node in the MST.
- Repeat: Continue this process until all nodes are included.
At each step, the algorithm expands the MST by selecting the edge with the least possible weight, ensuring the tree grows optimally.
Java Code
import java.io.*;
class Primal {
static int v = 0, e = 0, MAXNODE = 50, INFINITY = 10000;
static int adj[][] = new int[MAXNODE][MAXNODE]; // Adjacency matrix to represent the graph
static int visited[] = new int[MAXNODE]; // Tracks visited vertices
static int path[] = new int[MAXNODE]; // Stores parent of each node in MST
static int dist[] = new int[MAXNODE]; // Stores minimum weight to connect to MST
// Step 1: Build the adjacency matrix from user input
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: ");
v = Integer.parseInt(br.readLine());
System.out.print("Enter the number of Edges: ");
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 + ": ");
a = Integer.parseInt(br.readLine());
System.out.print("Destination " + i + ": ");
b = Integer.parseInt(br.readLine());
System.out.print("Weight " + i + ": ");
c = Integer.parseInt(br.readLine());
adj[a - 1][b - 1] = adj[b - 1][a - 1] = c; // Store edge weight in both directions (undirected graph)
System.out.println();
}
// Display adjacency matrix
System.out.println("\nAdjacency 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();
}
}
// Step 2: Apply Prim's algorithm to build the MST
static void prim(int start) throws IOException {
// Step 2.1: Initialize distances and visited array
for (int i = 0; i < v; i++) {
visited[i] = path[i] = 0;
dist[i] = INFINITY;
}
int nv = 1, curr = start, min;
visited[curr] = 1; // Step 2.2: Start with the initial node
while (nv != v) {
// Step 2.3: Update distances to adjacent unvisited nodes
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]; // Update the shortest edge to unvisited node
path[j] = curr; // Store current node as parent
}
}
}
// Step 2.4: Find the next node with the smallest distance
min = INFINITY;
for (int j = 0; j < v; j++) {
if (visited[j] != 1 && dist[j] < min) {
min = dist[j];
curr = j;
}
}
// Step 2.5: Mark this node as visited
visited[curr] = 1;
nv++;
}
// Step 3: Output total cost of MST
int c = 0;
for (int j = 1; j < v; j++)
c += dist[j];
System.out.println("\nThe minimum cost of spanning tree is: " + c);
// Step 4: Output the MST edges
System.out.println("\nMinimum spanning tree is as follows:");
for (int i = 1; i < v; i++)
System.out.println("Vertex " + (i + 1) + " is connected to vertex " + (path[i] + 1));
}
public static void main(String[] args) throws IOException {
buildGraph(); // Build the graph from user input
prim(0); // Start Prim's algorithm from vertex 0
}
}
Sample 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
Adjacency 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:
Vertex 2 is connected to vertex 1
Vertex 3 is connected to vertex 2
Vertex 4 is connected to vertex 5
Vertex 5 is connected to vertex 2Output Explanation
- The algorithm starts from vertex 1 (index 0 internally).
- It selects vertex 2 through the shortest available edge (weight 2).
- Then it includes vertex 3 connected from vertex 2 (weight 6).
- Next, it chooses vertex 5 through vertex 2 (weight 7).
- Finally, vertex 4 is connected via vertex 5 (weight 4).
- All selected edges contribute to the total MST cost of 19.
The final MST includes the edges with weights: 2, 6, 7, and 4, which span all five vertices with no cycles and minimal total cost.
Final Thoughts
Prim’s algorithm is an efficient way to find a minimum spanning tree for a graph. By always choosing the edge with the smallest weight that connects to an unvisited node, it guarantees an optimal spanning tree with minimal cost.
“Efficiency is doing better what is already being done.” – Peter Drucker