# 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)*.