# Prim’s Algorithm for MST(with Code Walkthrough) | GeeksforGeeks

Articles, Blog 37 Comments

Prim’s algorithm for computing the minimum

spanning tree of a graph. Now, let’s start off with some basic definitions.

What is a spanning tree? A spanning tree is a subgraph that has the same vertex set as the

original graph and is also a tree which means that it must be connected and must not contain

any cycles. A graph may have large number of spanning trees but not all of them are

minimum. A minimum spanning tree is the one in which the sum of weight of edges is minimum.

For example, consider the graph shown here. The edges highlighted in yellow are the edges

of the spanning tree. Now, both the trees shown here form a spanning tree because each

of these contain all the 4 vertices, are connected and do not contain any cycles. But

tree 2 here a cost lower than tree 1. Infact, tree 2 is a minimum spanning tree, so the

sum of weights of its edges would be lower than any other possible spanning tree of the graph.

Step’s for finding minimum spanning tree using prim’s algorithm. Well it would be

better if we try and understand each step one by one

with the help of an example. So, let’s do that.

Consider the given graph which has 9 vertices, v0 to v8. The numbers on the edges represent the weight of that edge. We need to obtain

a minimum spanning tree of the given graph. The 1 st step says create a set mstSet which

will contain all the vertices in MST. Initially, this set will be empty of course.

Let’s look at step 2. It says that initialize the key of all vertices except the source

vertex to infinity. The source vertex is assigned key

0. Basically, the key of every vertex stores the weight of the minimum weighted edge it is

connected to such that the other end point of the edge is a vertex in mstSet. It’ll be

clearer as we proceed through the example. The next step says that we need to pick a

vertex u not in mstSet with minimum key value. Since, no vertex is in mstSET initially, we

need to look at all the vertices. Here, v0 has a key 0 while all other vertices have key infinite.

So, v0 has the minimum key and hence it’ll be added to our mstSet.

Now, here, the vertices in red represent those that our added to the MstSet while those in orange represent all vertices adjacent to

our current vertex u which are not in mstSET. According to the next step, we need to update

the key values of all vertices adjacent to u which are v1 and v7 in this case. Now, how

to update the key values? It’s simple. If the weight of edge uv is less than the key of

v, update the key value as weight of uv. We see that weight of edge 0,1 is 4 while the key of 1

is still infinite. So, we’ll update the key of v1 to 4. Similarly, the weight of edge 0,7 which is

8 is less than key of 7 which is again infinite. It implies we need to update the key of v7 to

8. Again, pick the vertex with minimum key not

in MSTset which is v1 in this case with key 4. Add it to mstSet.

Here, v2 and v7 are vertices adjacent to u. Now, we again see that weight of edge 1,2

which is 8 is less than the current key of v2. So,

key of v2 will be updated to 8. But on the other hand, weight of edge 1,7 is 11 whereas the

key of v7 is already 8. So, key of v7 won’t be updated.

Again, pick vertex with minimum key not in mstSet. Both v2 and v7 have lowest keys, so

you can add either to mstSet. Let’s add v7.

V8 and v6 are adjacent vertices of v7 not in mstSet. We’ll update their keys following

the same procedure as earlier.

Next vertex to pick is v6 which has the lowest key of 1.

V8 and v5 are vertices adjacent to our u i.e. v6. Weights of both v6v5 and v6v8 are less

than the keys of v5 and v8 respectively. Update

their keys too. Now, v5 will be picked because it has the

lowest key 2 among all the vertices not in mstSet.

Now, v5 has 3 adjacent vertices not in mstSet namely v2, v3 and v4. Keys of all the 3 will

be updated.

Among the 4 vertices not in mstSet, v2 has the lowest key.

With v2 as u, we find its neighbouring vertices not in mstSet, v3 and v8 and update their keys following the same rule as always!

Now, v8 has the lowest key – 2. Add it to mstSet.

We see that v8 has no vertex adjacent to it not already a part of mstSet. Thus, no keys

will be updated in this case.

V3 will be picked now because it’s key is less than that of v4, which is the only other

vertex left not in mstSet.

To update the keys, consider the only adjacent vertex of v3, which is v4. Its weight is less than the current key of v4 which was 10. So,

set v4’s key to 9. Pick the last remaining vertex v4 and add

it to mstSet. Note that our condition says the procedure

will continue till all vertices are not part of mstSet. Since all the vertices are now added

to mstSet, we have reached the terminating condition.

Thus, we have successfully obtained the minimum spanning tree of the given graph. We can also calculate the weight of this MST by adding

the weight of individual edges in this tree. We see that they add up to 37. The time complexity

of Prim’s algorithm is O(V^2) if implemented using adjacency matrix and O(ElogV)

if done using adjacency list and binary heap.

Now, let’s analyse the code for Prim’s algorithm. This is an adjacency matrix implementation of the algorithm. Let’s start with the main

function. We’ve initialized the graph with the following matrix. The graph contains 5 vertices

0 to 4. Here, 2 represents theres an edge between vertex 0 and 1 with weight 2, 6 represents

an edge between vertex 0 and 3 and so on. Now, we call this function. Parent array

stores our constructed MST. Key stores the key value of v, and mstSET keeps track of vertices

not yet included in the MST. Initially, we set key of all vertices as infinite and none of

them belong to mstSet yet. Then we set the key of source as 0 and it’s parent as -1 because

it doesn’t have any parent. Now, the 1 st line in this for loop picks the vertex u with minimum key

not in MST. Let’s see the function. It says that if the vertex has not yet been added to mstSet

and if it’s key is minimum, pick this vertex as u. Now, mstset[u]=true adds u to mstSet. In

the next for loop, we check for each vertex that if graph[u][v] is not 0 i.e. if u and v are

adjacent vertices and v is not yet added to mstSet, we check if weight(u,v) is less than current

key of v, we update the key of v as weight of u,v. And set v’s parent as u. Finally, this printMST

function will be called which prints the vertex u, vertex v and weight of edge u,v for each edge

in MST. Thank you for watching the video. Please leave

us your comments!

Subhamay SamantaPost authorVery Good Explanation

thetruerealityPost authorThroughout your explanation you have never mentioned how the parent array is used.

Prince Kumar SinghPost authorPlease improve the audio..

Nice explanation though

Shivangi KansalPost authorWhy do you speak like you're anchoring somewhere ðŸ˜‚ðŸ˜‚ðŸ˜‚

Rakesh YadavPost authorawsome bro

Vrishank GuptaPost authorAmazing!

Sandeep RPost authorgreat video. Keep it up. Thanks to 'geeksforgeeks' for quality videos

Manav SethiPost authoramazing explanation but shitty audio

Sanjay AnuchuriPost authorTooo bad at explaination…..

RuphinyPost authorVery good explanation!!

siddharth singhPost authorAt 3:48 when the key of both 2 and 7 are the same what if we choose vertex 2. A different st is formed.

Is that correct.

Saurav SinghPost authorawesome…..keep up the good work

vinay patelPost authorMy left ear didn't get it but right ear understand it..great explanation

Ahmad ButtPost authorOn which basis youâ€™ve selected adjacent 8 n 5 to 6, 8 and 7 are also adjacent to 6.

Mah TaajPost authorLike there is key 8 for both vertex 2 and 7 the selecting other one will lead to a different spanning tree. Is that so??

Anjaney SharmaPost authorAt 7:09 who checked their mobile phones?

Elliot LiuPost authorWhat is the time complexity of implementing this algorithm with an adjacency list and priority_queue?

no noPost authorP O O I N L O O

Abhishek KorangaPost authorbro work on the audio part of video…

Vedran KarajlicPost authorHow can we choose vertex to start from?

Debashish MishraPost authorMy right ear gained a lot of knowledge today. The left is still a dumb piece of cartilage.

Shehroze AslamPost authorPlz tell me the calculating time of prims algorithm which is implemented using SPQ (it is a special kind of priority queue)

Gurinder MaanPost authorHow do we apply the prims algorithm if the vertex are not digits but are alphabets??

Apoorva GuptaPost authorWorst explaination didnt expected this from geeks for geeks

Amar JitPost authorI don't understand the video

Rishi KaushikPost authorWin+U > audio > Turn on mono audio

raghav bansalPost authorv2 and v7 mai se agar v1 loge toh answer 39 aayega.

sanjay singhPost authorGreat video sir…

Ali EserPost authori had to watch the video a second time because my left ear got mad at me saying that I let the right one learn but not him

REassumePost authorThanks for making this vedio. The people who are complaining about your audio are the one who actually came here to focus on an unimportant thing.

Raghav GuptaPost authorExcellent ..

Marvellous … Clears concept…

Riya Ramesh.KPost authorThe best!

Anuprakash SharmaPost authorHow do you blow into the microphone, when using a robot voice

abhinav guptaPost authordude u even dont know ELOGV > V^2(becz E=V^2)

mÃ¼ptezel cihatPost authorgood thing the right part of my headphones wasnt totally dead

RUGVED BONGALEPost authorawesome explanation …thanks for the code

Master Piece TVPost authorGreat work GeekforGeeks.. I want to suggest that in your subsequent video try to create a small space where you can type your words as you teach.. Though you try to make it transparent, it was still a distraction.. Well done bro and keep the good job going