Earlier in our articles, we briefly discussed the Dijkstra’s Algorithm and implement Dijkstra’s algorithm using Java program. In this article, we discuss the **prims algorithm, **its practical applications and finally, we implement that algorithm using Java.

Contents

## WHAT IS PRIMS ALGORITHM?

It is an algorithm which is used to find the *minimum spanning tree *of the undirected graph. It uses the **greedy technique **to find the minimum spanning tree (MST) of the undirected graph. The greedy technique is the technique in which we need to select the *local optimal solution* with hope to find the global optimal solution. Like every algorithm, prims algorithm has many practical applications like:

- Many routing algorithms use this prims algorithm.
- If we need to minimize any electricity loss we can implement this algorithm and minimize the total cost of the wiring.
- You can find the minimum distance to transmit a packet from one node to another in large networks.
- It is used widely in topology and study of molecular bonds in chemistry.

**ALGORITHM:**

1: Get the number of vertices (n) and weight of the edges from the user.

2: Consider any vertex in graph process the vertex and add the vertex to the tree.

3: Find the smallest edge from the graph connecting the edge of the vertex in the tree such that it does not form a cycle.

4: Add the vertex to the tree.

5: Repeat from step 4, until tree contains all the n vertices.

Let us see how to implement this algorithm in Java programming. If you need to implement this algorithm in any other programming languages let us know in the comment section.

## PRIMS ALGORITHM USING JAVA :

import java.util.*; import java.lang.*; import java.io.*; class prims { 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] == false && key[v] < min) { min = key[v]; min_index = v; } return min_index; } void printMST(int parent[], int n, 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[][]) { // Array to store constructed MST int parent[] = new int[V]; // Key values used to pick minimum weight edge in cut int key[] = new int [V]; // To represent set of vertices not yet included in MST Boolean mstSet[] = new Boolean[V]; // Initialize all keys as INFINITE 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, V, graph); } public static void main (String[] args) { /* Let us create the following graph 2 3 (0)--(1)--(2) | / \ | 6| 8/ \5 |7 | / \ | (3)-------(4) 9 */ prims t = new prims(); 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}, }; // Print the solution t.primMST(graph); } }

The output of this program will be :

Hope this article will help you to understand the Prims Algorithm. If you are interested in programming do subscribe to our E-mail newsletter for all programming tutorials.