Prim’s Algorithm with a Java Implementation
Prim’s Algorithm is a popular Algorithm in the field of computer science and Graph Theory It is used to find the Minimum Spanning Tree of a weighted, undirected graph. The Minimum Spanning Tree is the subset of the Graph that connects all vertices with minimum total edge weight that is also without forming any cycle. In this article we explain about How to implement Prim’s Algorithm with Java programming with required operations like adding edges, Graph Initialization and Setting the Starting Point in Prim’s Algorithm, Building the MST and other operations.
What is Prim’s Algorithm Used For?
Prim’s Algorithm is commonly used in network design, such as planning telecommunication, electrical grids and transportation networks. Where the goal is to connect all nodes with the least amount of cost or distance. Finally, It constructs an optimal network in various fields.
Explanation of Steps with an Example:
Graph Structure:
The graph has 4 vertices (0, 1, 2, 3) and 5 edges with the following weights
- Edge from vertex 0 to 1 with a weight of 10.
- Edge from vertex 0 to 2 with a weight of 6.
- Edge from vertex 0 to 3 with a weight of 5.
- Edge from vertex 1 to 3 with a weight of 15.
- Edge from vertex 2 to 3 with a weight of 4.
Minimum Spanning Tree:
Kruskal’s algorithm sorts the edges by weight, then iterates through the edges to include them in the MST if they don’t create a cycle.
- Edge from vertex 2 to 3 with a weight of 4
- Edge from vertex 0 to 3 with a weight of 5
- Edge from vertex 0 to 1 with a weight of 10
These edges connect all four vertices without creating cycles, forming the Minimum Spanning Tree with the minimum total weight 19.
Where Prim’s Algorithm is Used:
- Designing cost-efficient communication networks
- Building minimum-cost electrical grids or pipelines
- Organizing road networks to minimize construction costs
Pseudo code for Prim’s Algorithm:
Here’s a simple pseudo code for Prim’s Algorithm
function prim(graph):
create a set called MST (minimum spanning tree)
create a priority queue (min-heap) for edges, initialized with a random edge
create a set to keep track of visited nodes
while the priority queue is not empty:
edge = priority_queue.pop()
if edge's end node is not in visited nodes:
add edge to MST
add edge's end node to visited nodes
for each edge connected to edge's end node:
if the other end of the edge is not in visited nodes:
add the edge to the priority queue
return MST
Java Implementation of Prim’s Algorithm:
// Java Program to Implement Prim's Algorithm
import java.util.*;
// Class to represent an edge in the graph
class Edge {
int source;
int dest;
int weight;
// Constructor to initialize an edge
Edge(int source, int dest, int weight) {
this.source = source;
this.dest = dest;
this.weight = weight;
}
}
// Class to represent the graph
class Graph {
int vertices;
LinkedList<Edge>[] adjacencyList;
// Constructor to initialize the graph with
// the given number of vertices
Graph(int vertices) {
this.vertices = vertices;
adjacencyList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adjacencyList[i] = new LinkedList<>();
}
}
// Method to add an edge to the graph
void addEdge(int source, int dest, int weight) {
Edge edge = new Edge(source, dest, weight);
adjacencyList[source].add(edge);
// Adding the reverse edge since it's an undirected graph
adjacencyList[dest].add(new Edge(dest, source, weight));
}
// Method to implement Prim's algorithm to
// find the Minimum Spanning Tree (MST)
void primMST() {
// Array to keep track of vertices included in MST
boolean[] inMST = new boolean[vertices];
// Priority queue to select the edge
// with the smallest weight
PriorityQueue<Edge> priorityQueue =
new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
// List to store the MST edges
List<Edge> mst = new ArrayList<>();
// Start from any vertex, here it's 0
int startVertex = 0;
// Mark the start vertex as included in MST
inMST[startVertex] = true;
// Add all edges from the start vertex to the priority queue
for (Edge edge : adjacencyList[startVertex]) {
priorityQueue.add(edge);
}
// Process the edges in the priority queue
while (!priorityQueue.isEmpty()) {
// // Get the edge with the smallest weight
Edge currentEdge = priorityQueue.poll();
// If the destination vertex is not yet
// included in MST
if (!inMST[currentEdge.dest]) {
// Add the edge to the MST
mst.add(currentEdge);
// Mark the destination vertex as included in MST
inMST[currentEdge.dest] = true;
// Add all edges from the current edge's
// destination to the priority queue
for (Edge edge : adjacencyList[currentEdge.dest]) {
if (!inMST[edge.dest]) {
priorityQueue.add(edge);
}
}
}
}
// Print the edges in the MST
System.out.println("Minimum Spanning Tree:");
for (Edge edge : mst) {
System.out.println("Edge: " + edge.source + " - "
+ edge.dest + " Weight: " + edge.weight);
}
}
}
// Main class to test the Prim's algorithm implementation
public class PrimAlgorithmExample {
public static void main(String[] args) {
// Create a graph with 4 vertices
Graph graph = new Graph(4);
// Add edges to the graph
graph.addEdge(0, 1, 1);
graph.addEdge(1, 2, 2);
graph.addEdge(2, 3, 3);
graph.addEdge(0, 3, 4);
// Find and print the MST using Prim's algorithm
graph.primMST();
}
}
Output
Minimum Spanning Tree: Edge: 0 - 1 Weight: 1 Edge: 1 - 2 Weight: 2 Edge: 2 - 3 Weight: 3
Advantages and Disadvantages of using Prim’s Algorithm
Advantages
- Efficient for finding a minimum spanning tree in dense graphs
- Simple and intuitive approach using a greedy method.
Disadvantages
- Can be less efficient than other Minimum Spanning Tree algorithms like Kruskal’s for sparse graphs
- Requires a data structure like a min-heap to achieve optimal time complexity.
Applications
- In Networking design mostly The Minimum Spanning Tree is used.
- For identifying natural clustering in Graph.
- Used in approximation algorithms for problems like Travelling Salesman Problem.
- Constructing efficient road or pipelines network with minimal construction costs.