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!

Very Good Explanation

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

Please improve the audio..

Nice explanation though

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

awsome bro

Amazing!

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

amazing explanation but shitty audio

Tooo bad at explaination…..

Very good explanation!!

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.

awesome…..keep up the good work

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.

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

At 7:09 who checked their mobile phones?

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

P O O I N L O O

bro work on the audio part of video…

How can we choose vertex to start from?

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

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

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

Worst explaination didnt expected this from geeks for geeks

I don't understand the video

Win+U > audio > Turn on mono audio

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

Great video sir…

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

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.

Excellent ..

Marvellous … Clears concept…

The best!

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

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

good thing the right part of my headphones wasnt totally dead

awesome explanation …thanks for the code

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

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

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.

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

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