# Prim’s Algorithm in C [Program & Algorithm]

Here you will learn about prim’s algorithm in C with a program example.

Prim’s Algorithm is an approach to determine minimum cost spanning tree. In this case, we start with single edge of graph and we add edges to it and finally we get minimum cost tree. In this case, as well, we have n-1 edges when number of nodes in graph are n.We again and again add edges to tree and tree is extended to create spanning tree, while in case of Kruskal’s algorithm there may be more than one tree, which is finally connected through edge to create spanning tree.

### Algorithm

This algorithm creates spanning tree with minimum weight from a given weighted graph.

1. Begin
2. Create edge list of given graph, with their weights.
3. Draw all nodes to create skeleton for spanning tree.
4. Select an edge with lowest weight and add it to skeleton and delete edge from edge list.
5. Add other edges. While adding an edge take care that the one end of the edge should always be in the skeleton tree and its cost should be minimum.
6. Repeat step 5 until n-1 edges are added.
7. Return.

## Program for Prim’s Algorithm in C

C program for constructing a minimum cost spanning tree of a graph using Prim’s algorithm is given below.

Output

Enter no. of vertices:6

0 3 1 6 0 0
3 0 5 0 3 0
1 5 0 5 6 4
6 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0

spanning tree matrix:

0 3 1 0 0 0
3 0 0 0 3 0
1 0 0 0 0 4
0 0 0 0 0 2
0 3 0 0 0 0
0 0 4 2 0 0

Total cost of spanning tree=13

#### Time Complexity

Prim’s algorithm contains two nested loops. Each of this loop has a complexity of O (n). Thus, the complexity of Prim’s algorithm for a graph having n vertices = O (n2).

Comment below if you found anything incorrect or missing in above prim’s algorithm in C.

Category: Algorithm DSA A crazy computer and programming lover. He spend most of his time in programming, blogging and helping other programming geeks.

## 11 thoughts on “Prim’s Algorithm in C [Program & Algorithm]”

1. bibhu ranjan

please give an explanation on the following snipet of the above code

u=from[v]; //what is u and v here…??

//insert the edge in spanning tree
spanning[u][v]=distance[v];
spanning[v][u]=distance[v];
no_of_edges–;
visited[v]=1;

//updated the distance[] array
for(i=1;i<n;i++)
if(visited[i]==0&&cost[i][v]<distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}

2. PRAKHAR GANDHI

u is parent of v .After first initialization,parent is set from G to G[v] .Since it is undirected graph we have to set equal values in both direction for [u][v] and [v][u].After visting vertex 0,do the same for n-2 non visited vertices.

1. Arifur Rahman

what is the purpose of ” from[i]=v ” ?

3. Rahul Bose

Can’t understand the algorithm behind this code properly….Please explain what are we storing in visited,distance and from arrays….An allover better explanation will definitely help very much.

4. Bhavesh

Can u plz add example of prims algorithmas similar to krushkal algo. for the easy understanding

5. Karan Dubey from NMIMS

Why is it necessary for every student to learn this algorithm when its already available on internet????
Why?

1. Sonia

Exactly!!!!!!

2. Vikas Patel

agree

6. shubham

how does it checks wheather there is formation of cycle in spanning tree ?

7. Salah

This is not the code for Prims, for prims it is necessary to be able to pick the node from where you start. Also Prims doesnt need the union find datastructure which seems you implemented with the part where you set the parent from G to G[v] after first initialization. This is just another implementation of Kruskal where you start with the lowest edge. This may cause some confusion.

8. codemonkey

It worked well for my case thanks a lot!!