In this tutorial, you will learn **Prim’s Algorithm** works. Additionally, you will discover working instances of Prim’s Algorithm in C, C++, Java, and Python.

Contents

## What is Prim’s algorithm?

**Prim’s algorithm** is a greedy algorithm i.e., it picks an optimal way at each point and at last tracks down the briefest way by making a spanning tree.

Prims algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which

- structure a tree that incorporates each vertex
- has the base amount of weights among every one of the trees that can be formed from the graph

## How Prim’s algorithm works

It falls under a class of algorithms considered greedy algorithms that track down the local optimum with expectations of tracking down a global optimum.

We start from one vertex and continue to add edges with the most reduced weight until we arrive at our objective.

The steps for executing Prim’s algorithm are as per the following:

- Instate the minimum spanning tree with a vertex picked random.

2. Track down every one of the edges that associate the tree to new vertices, track down the base and add it to the tree

3. Continue repeating stage 2 until we get a minimum spanning tree

## Example of Prim’s algorithm

## Prim’s Algorithm pseudocode

The pseudocode for Prims algorithm shows how we create two arrangements of vertices U and V-U. U contains the list of vertices that have been visited and V-U the list of vertices that haven’t. Individually, we move vertices from set V-U to set U by associating the least weight edge.

T = ∅; U = { 1 }; while (U ≠ V) let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U; T = T ∪ {(u, v)} U = U ∪ {v}

## Python, Java, and C/C++ Examples

Despite the fact that the adjacency matrix representation of graphs is used, this algorithm can likewise be carried out using Adjacency List to improve its productivity.

**Python**

# Prim's Algorithm in Python INF = 9999999 # number of vertices in graph V = 5 # create a 2d array of size 5x5 # for adjacency matrix to represent graph G = [[0, 9, 75, 0, 0], [9, 0, 95, 19, 42], [75, 95, 0, 51, 66], [0, 19, 51, 0, 31], [0, 42, 66, 31, 0]] # create a array to track selected vertex # selected will become true otherwise false selected = [0, 0, 0, 0, 0] # set number of edge to 0 no_edge = 0 # the number of egde in minimum spanning tree will be # always less than(V - 1), where V is number of vertices in # graph # choose 0th vertex and make it true selected[0] = True # print for edge and weight print("Edge : Weight\n") while (no_edge < V - 1): # For every vertex in the set S, find the all adjacent vertices #, calculate the distance from the vertex selected at step 1. # if the vertex is already in the set S, discard it otherwise # choose another vertex nearest to selected vertex at step 1. minimum = INF x = 0 y = 0 for i in range(V): if selected[i]: for j in range(V): if ((not selected[j]) and G[i][j]): # not in selected and there is an edge if minimum > G[i][j]: minimum = G[i][j] x = i y = j print(str(x) + "-" + str(y) + ":" + str(G[x][y])) selected[y] = True no_edge += 1

**Java**

// Prim's Algorithm in Java import java.util.Arrays; class PGraph { public void Prim(int G[][], int V) { int INF = 9999999; int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false boolean[] selected = new boolean[V]; // set selected false initially Arrays.fill(selected, false); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in // graph // choose 0th vertex and make it true selected[0] = true; // print for edge and weight System.out.println("Edge : Weight"); while (no_edge < V - 1) { // For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise // choose another vertex nearest to selected vertex at step 1. int min = INF; int x = 0; // row number int y = 0; // col number for (int i = 0; i < V; i++) { if (selected[i] == true) { for (int j = 0; j < V; j++) { // not in selected and there is an edge if (!selected[j] && G[i][j] != 0) { if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } System.out.println(x + " - " + y + " : " + G[x][y]); selected[y] = true; no_edge++; } } public static void main(String[] args) { PGraph g = new PGraph(); // number of vertices in grapj int V = 5; // create a 2d array of size 5x5 // for adjacency matrix to represent graph int[][] G = { { 0, 9, 75, 0, 0 }, { 9, 0, 95, 19, 42 }, { 75, 95, 0, 51, 66 }, { 0, 19, 51, 0, 31 }, { 0, 42, 66, 31, 0 } }; g.Prim(G, V); } }

**C**

// Prim's Algorithm in C #include<stdio.h> #include<stdbool.h> #define INF 9999999 // number of vertices in graph #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G[V][V] = { {0, 9, 75, 0, 0}, {9, 0, 95, 19, 42}, {75, 95, 0, 51, 66}, {0, 19, 51, 0, 31}, {0, 42, 66, 31, 0}}; int main() { int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected[V]; // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected[0] = true; int x; // row number int y; // col number // print for edge and weight printf("Edge : Weight\n"); while (no_edge < V - 1) { //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) { if (selected[i]) { for (int j = 0; j < V; j++) { if (!selected[j] && G[i][j]) { // not in selected and there is an edge if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } printf("%d - %d : %d\n", x, y, G[x][y]); selected[y] = true; no_edge++; } return 0; }

**C++**

// Prim's Algorithm in C++ #include <cstring> #include <iostream> using namespace std; #define INF 9999999 // number of vertices in grapj #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G[V][V] = { {0, 9, 75, 0, 0}, {9, 0, 95, 19, 42}, {75, 95, 0, 51, 66}, {0, 19, 51, 0, 31}, {0, 42, 66, 31, 0}}; int main() { int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected[V]; // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected[0] = true; int x; // row number int y; // col number // print for edge and weight cout << "Edge" << " : " << "Weight"; cout << endl; while (no_edge < V - 1) { //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) { if (selected[i]) { for (int j = 0; j < V; j++) { if (!selected[j] && G[i][j]) { // not in selected and there is an edge if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } cout << x << " - " << y << " : " << G[x][y]; cout << endl; selected[y] = true; no_edge++; } return 0; }

## Prim’s vs Kruskal’s Algorithm

Kruskal’s algorithm is another famous minimum spanning tree algorithm that uses an alternate logic to discover the MST of a graph. Rather than beginning from a vertex, Kruskal’s algorithm sorts every one of the edges from low weight to high and continues adding the most minimal edges, disregarding those edges that create a cycle.

## Prim Algorithm Complexity

The time complexity of Prims algorithm is O(E log V).

## Prim Algorithm Application

- Laying cables of electrical wiring
- In-network designed
- To make protocols in network cycles

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.