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

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
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

## 41 thoughts to “Prim’s Algorithm for MST(with Code Walkthrough) | GeeksforGeeks”

1. Subhamay Samanta says:

Very Good Explanation

2. thetruereality says:

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

3. Prince Kumar Singh says:

Nice explanation though

4. Shivangi Kansal says:

Why do you speak like you're anchoring somewhere 😂😂😂

awsome bro

6. Vrishank Gupta says:

Amazing!

7. Sandeep R says:

great video. Keep it up. Thanks to 'geeksforgeeks' for quality videos

8. Manav Sethi says:

amazing explanation but shitty audio

9. Sanjay Anuchuri says:

10. Ruphiny says:

Very good explanation!!

11. siddharth singh says:

At 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.

12. Saurav Singh says:

awesome…..keep up the good work

13. vinay patel says:

My left ear didn't get it but right ear understand it..great explanation

On which basis you’ve selected adjacent 8 n 5 to 6, 8 and 7 are also adjacent to 6.

15. Mah Taaj says:

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

16. Anjaney Sharma says:

At 7:09 who checked their mobile phones?

17. Elliot Liu says:

What is the time complexity of implementing this algorithm with an adjacency list and priority_queue?

18. NaN says:

P O O I N L O O

19. Abhishek Koranga says:

bro work on the audio part of video…

20. Vedran Karajlic says:

How can we choose vertex to start from?

21. Debashish Mishra says:

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

22. Shehroze Aslam says:

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

23. Gurinder Maan says:

How do we apply the prims algorithm if the vertex are not digits but are alphabets??

24. Apoorv Gupta says:

Worst explaination didnt expected this from geeks for geeks

25. Amar Jit says:

I don't understand the video

26. Rishi Kaushik says:

Win+U > audio > Turn on mono audio

27. raghav bansal says:

v2 and v7 mai se agar v1 loge toh answer 39 aayega.

28. sanjay singh says:

Great video sir…

29. Ali Eser says:

i 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

30. REassume says:

Thanks 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.

31. Raghav Gupta says:

Excellent ..
Marvellous … Clears concept…

32. Riya Ramesh.K says:

The best!

33. Anuprakash Sharma says:

How do you blow into the microphone, when using a robot voice

34. abhinav gupta says:

dude u even dont know ELOGV > V^2(becz E=V^2)

35. müptezel cihat says:

36. RUGVED BONGALE says:

awesome explanation …thanks for the code

37. Master Piece TV says:

Great 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

38. Uesugi Kenshin says:

first time didn't get any geekforgeeks explanation. T.T my head is hurting now.

39. Shashank Kumar says:

https://youtu.be/eB61LXLZVqs?t=361

You did not mention that we expect to update minHeap after looking at a key and since Java does not provide this api, you are using O(V^2) approach.

40. Shubham Kumar says:

Now my right half of brain is smarter than the left half. Thank you.

41. Akash Thakur says:

Madarchod jisne job sequence aur activity selection padhaya usko BULA, bhen k lode mood kharab kar Dia tune