Implementing Prim’s Algorithm in Java

---

Mastering Prim’s Algorithm: Unveiling the Minimum Spanning Tree (MST) in Java

Prim’s algorithm is a cornerstone of graph theory, designed to find the Minimum Spanning Tree (MST) of a weighted, undirected graph efficiently. Understanding its principles and implementation in Java is essential for any serious programmer or computer science enthusiast.

Understanding Prim’s Algorithm

Prim’s algorithm operates by starting from an arbitrary vertex and iteratively growing the MST by adding the smallest-weight edge that connects a vertex in the MST to one outside of it. This method ensures that the MST remains connected with the minimal possible total weight.

Key Concepts and Steps

1. Initialization: Begin with an empty set that will eventually form the MST. Select an arbitrary starting vertex to kick off the algorithm.
2. Edge Selection: Continuously add the edge with the smallest weight that connects a vertex in the MST to a vertex outside of it, ensuring no cycles are formed.
3. Priority Queue: Use a priority queue to efficiently retrieve the smallest-weight edge available for inclusion in the MST at each step.
4. Algorithm Execution: Repeat the process until all vertices are included in the MST, resulting in a tree that spans all vertices with the minimal total weight.

Java Implementation

Let’s delve into a Java implementation of Prim’s algorithm to solidify our understanding:

PrimsAlgorithm Class

import java.util.*;

class PrimsAlgorithm {
    int source, destination, weight;

    public PrimsAlgorithm(int source, int destination, int weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }
}

• Explanation: The PrimsAlgorithm class represents an edge in the graph with attributes source, destination, and weight.

Graph Class

class Graph {
    private List<List<PrimsAlgorithm>> adjList;
    private int vertices;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);

        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination, int weight) {
        adjList.get(source).add(new PrimsAlgorithm(source, destination, weight));
        adjList.get(destination).add(new PrimsAlgorithm(destination, source, weight));
    }

    public void primMST() {
        boolean[] inMST = new boolean[vertices];
        PriorityQueue<PrimsAlgorithm> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        PrimsAlgorithm[] result = new PrimsAlgorithm[vertices - 1];
        int edgeIndex = 0;

        inMST[0] = true;
        pq.addAll(adjList.get(0));

        while (edgeIndex < vertices - 1 && !pq.isEmpty()) {
            PrimsAlgorithm edge = pq.poll();

            if (inMST[edge.destination]) {
                continue;
            }

            inMST[edge.destination] = true;
            result[edgeIndex++] = edge;

            for (PrimsAlgorithm nextEdge : adjList.get(edge.destination)) {
                if (!inMST[nextEdge.destination]) {
                    pq.add(nextEdge);
                }
            }
        }

        System.out.println("Edges in the Minimum Spanning Tree:");
        for (PrimsAlgorithm edge : result) {
            if (edge != null) {
                System.out.println(edge.source + " - " + edge.destination + ": " + edge.weight);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 2, 6);
        graph.addEdge(0, 3, 5);
        graph.addEdge(1, 3, 15);
        graph.addEdge(2, 3, 4);

        graph.primMST();
    }
}

• Explanation: The Graph class implements the graph structure and the primMST method applies Prim’s algorithm to find the MST.

Conclusion

Prim’s algorithm is not just a theoretical concept but a powerful tool in network design, clustering, and more. Mastering its implementation in Java enhances your problem-solving skills and prepares you for tackling complex graph-related challenges in your projects.

---