Prim's Algorithm :Java Implementation

Introduction:

Prim's algorithm is a greedy algorithm for finding the minimum spanning tree in a weighted undirected graph. A minimum spanning tree is a tree that spans all vertices in a graph and has the minimum possible total edge weight. The algorithm works by maintaining a set of vertices that have already been included in the minimum spanning tree and iteratively adding the next closest vertex to this set.

Here's an example implementation of Prim's algorithm in Java:

import java.util.*;

class PrimsAlgorithm {
    static int V = 5;

    int minKey(int key[], Boolean mstSet[]) {
        int min = Integer.MAX_VALUE, minIndex = -1;

        for (int v = 0; v < V; v++)
            if (mstSet[v] == false && key[v] < min) {
                min = key[v];
                minIndex = v;
            }

        return minIndex;
    }

    void printMST(int parent[], int graph[][]) {
        System.out.println("Edge   Weight");
        for (int i = 1; i < V; i++)
            System.out.println(parent[i] + " - " + i + "    " + graph[i][parent[i]]);
    }

    void primMST(int graph[][]) {
        int parent[] = new int[V];
        int key[] = new int[V];
        Boolean mstSet[] = new Boolean[V];

        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;
            for (int v = 0; v < V; v++)
                if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
        }

        printMST(parent, graph);
    }

    public static void main(String[] args) {
        int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 },
                { 0, 5, 7, 9, 0 } };
        PrimsAlgorithm t = new PrimsAlgorithm();
        t.primMST(graph);
    }
}

In this code, we first initialize arrays to store the minimum key values, parent nodes, and the set of vertices included in the minimum spanning tree. The minKey function returns the vertex with the minimum key value that has not yet been included in the minimum spanning tree. The primMST function implements the main logic of Prim's algorithm by iteratively adding vertices to the minimum spanning tree set and updating the key values and parent nodes based on the weights of the edges. The final

minimum spanning tree is printed in the printMST function.

The input for the algorithm is a weighted adjacency matrix graph representing the undirected graph. The algorithm starts with vertex 0 as the first vertex in the minimum spanning tree and its key value set to 0. In each iteration, the vertex with the minimum key value that has not been included in the minimum spanning tree is selected and its key value and parent node are updated based on the weights of its adjacent vertices. This process continues until all vertices have been included in the minimum spanning tree.

Time Complexity: O(V^2), where V is the number of vertices in the graph.

Space Complexity: O(V), as the algorithm uses arrays to store the key values, parent nodes, and the set of vertices included in the minimum spanning tree.

Output :

Let's consider the following weighted adjacency matrix graph representing an undirected graph with 5 vertices:

0	2	0	6	0
2	0	3	8	5
0	3	0	0	7
6	8	0	0	9
0	5	7	9	0

The output of the Prim's algorithm applied to this graph would be the minimum spanning tree represented by the following parent array:

-1	0	1	1	2

This means that the vertex 0 is the root of the minimum spanning tree and its parent is -1. Vertex 1 is a child of vertex 0 and its parent is 0. Vertex 2 is a child of vertex 1 and its parent is 1. Vertex 3 is a child of vertex 1 and its parent is 1. Vertex 4 is a child of vertex 2 and its parent is 2.

The minimum spanning tree can be visualized as:

	0
   / \
  1   4
 / \
2   3

This output represents the minimum spanning tree of the given graph with total weight 15, which is the sum of weights of all edges in the minimum spanning tree.