1. Introduction

Prim’s Algorithm is a greedy algorithm that is used to find a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

2. Program Steps

1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.

2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.

3. Repeat step 2 (until all vertices are in the tree).

3. Code Program

import java.util.Arrays;

class PrimAlgorithm {
    private static final int V = 5;

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

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

    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] && 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}};
        PrimAlgorithm pa = new PrimAlgorithm();
        pa.primMST(graph);
    }
}

Output:

Edge   Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5

4. Step By Step Explanation

1. V: Number of vertices in the graph.

2. minKey(int key[], Boolean mstSet[]): A utility function to find the vertex with the minimum key value, from the set of vertices not yet included in MST.

3. printMST(int parent[], int graph[][]): A utility function to print the constructed MST.

4. primMST(int graph[][]): Function to construct and print the MST for a graph represented using an adjacency matrix representation.

5. Inside primMST:

– parent[]: Array to store the constructed MST.

– key[]: Key values used to pick minimum weight edge in cut.

– mstSet[]: To represent the set of vertices included in MST.

– The loop continues until all vertices are included in the MST, and the minKey function helps find the minimum value vertex.

6. The main function provides a sample graph represented as an adjacency matrix and then invokes the primMST method to find and print the MST.

The time complexity of Prim's algorithm with an adjacency matrix representation is O(V^2).