Java Prim's Algorithm Tutorial 🎯

Welcome to this comprehensive guide on Java Prim's Algorithm! This tutorial is designed to help both beginners and intermediates understand and implement this essential graph traversal technique. Let's dive in!

Understanding Prim's Algorithm 📝

Prim's Algorithm is a popular method used for finding the minimum spanning tree (MST) in a connected, undirected graph. It works by gradually building the MST one vertex at a time, ensuring that the added vertex connects to the existing MST with the smallest edge possible.

Implementing Prim's Algorithm in Java 💡

Pseudo Code

Here's a simplified version of Prim's Algorithm:

Initialize a boolean array visited to indicate whether a vertex is included in the MST or not.
Initialize an empty Minimum Spanning Tree (MST) and a priority queue (min-heap) to store the unvisited vertices.
Add the first vertex to the MST and the priority queue.
While the priority queue is not empty:
- Dequeue the smallest vertex u from the priority queue.
- If u is not yet visited:
  - Mark u as visited.
  - Traverse its adjacent vertices v and update the priority queue if v is not yet visited and the edge (u, v) has the smallest weight among the edges connecting u and v to the current MST.
The resulting MST is stored in the priority queue.

Code Example 1: Minimum Spanning Tree (MST)

java

import java.util.*;

class Edge implements Comparable<Edge> {
    int v, w;

    Edge(int v, int w) {
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(Edge other) {
        return this.w - other.w;
    }
}

public class MinimumSpanningTree {
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int n = scanner.nextInt();
        List<Edge>[] graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        int m = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            graph[u].add(new Edge(v, w));
            graph[v].add(new Edge(u, w));
        }
        PrimMST(graph, n);
    }

    private static void PrimMST(List<Edge>[] graph, int n) {
        boolean[] visited = new boolean[n + 1];
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        visited[1] = true;
        pq.add(new Edge(1, 0));

        List<Edge> mst = new ArrayList<>();
        while (!pq.isEmpty()) {
            Edge u = pq.poll();
            int v = u.v;
            if (!visited[v]) {
                visited[v] = true;
                for (Edge edge : graph[v]) {
                    int w = edge.w;
                    int wv = edge.v;
                    if (!visited[wv] && w > u.w) {
                        pq.add(edge);
                    }
                }
                mst.add(u);
            }
        }

        System.out.println("Edge Weight of MST:");
        for (Edge edge : mst) {
            System.out.println(edge.v + " - " + edge.w + " - " + edge.v);
        }
    }
}

Code Example 2: Adjacency List Representation 💡

java

import java.util.*;

class Edge implements Comparable<Edge> {
    int v, w;

    Edge(int v, int w) {
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(Edge other) {
        return this.w - other.w;
    }
}

public class MinimumSpanningTree {
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int n = scanner.nextInt();
        Map<Integer, List<Edge>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }
        int m = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            graph.get(u).add(new Edge(v, w));
        }
        PrimMST(graph, n);
    }

    private static void PrimMST(Map<Integer, List<Edge>> graph, int n) {
        boolean[] visited = new boolean[n + 1];
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        visited[1] = true;
        pq.add(new Edge(1, 0));

        List<Edge> mst = new ArrayList<>();
        while (!pq.isEmpty()) {
            Edge u = pq.poll();
            int v = u.v;
            if (!visited[v]) {
                visited[v] = true;
                for (Edge edge : graph.get(v)) {
                    int w = edge.w;
                    int wv = edge.v;
                    if (!visited[wv] && w > u.w) {
                        pq.add(edge);
                    }
                }
                mst.add(u);
            }
        }

        System.out.println("Edge Weight of MST:");
        for (Edge edge : mst) {
            System.out.println(edge.v + " - " + edge.w + " - " + edge.v);
        }
    }

    static class Edge {
        int v, w;

        Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
}

Quiz

That concludes our tutorial on Java Prim's Algorithm. Keep practicing, and soon you'll be able to implement it in various real-world scenarios! 🎉