Hello friends my name is Tushar and

today we’re going to talk about how to find minimum spanning tree using Prim’s

algorithm.In another video I talked about how to find minimum spanning trees

using Kruskal’s algorithm and both Prim and Kruskal algorithms are greedy

algorithms. So what is the spanning tree of an undirected

graph? A spanning tree is a subgraph of a graph such that all ‘n’ vertices are

connected to each other and there are total n-1 edges in the subgraph.

So basically there is no cycle in this subgraph.What is a minimum spanning

tree? A minimum spanning tree is a spanning tree of weighted undirected graph such that the sum of

the weight of the edges is minimum. So suppose we have this graph here, here we have 4 vertices A,B,C,D,if we

pick 3, this 3 edges (A,B),(B,C) and (C,D),we get a

minimum spanning tree and the sum of their weights is one 1+1+1,that is

3.For Prim’s algorithm we need a binary heaps which supports decrease key

operation and which also supports contains and find operation. So in the next section let’s quickly

look at this data structure before talking Prim’s tree,prim’s algorithm.

Also if you don’t know what binary heap is I highly recommend you to read about

binary heap before watching this video. Our minimum binary heap or priority queue needs to

support these four operations-extractMin, add,contains and decrease. It,a regular binary heap already

supports extractMin and add in O(logn) time and O(logn) time and we also need

to support contains and decrease on O(1) time and O(logn) time. Let’s see how this works.So if we know

about regular minimum binary tree,we know that value at every node is less

than or equal to both its children. So -1 is less than equal to 2 and 6,2

is less than equal to 4 and 5,6 is less than equal to 7 and 8.So this satisfies all

the properties of minimum binary heap. Also we know that the values of the

minimum binary heap are stored in array. So this is just a logical diagram.In

reality this pair is stored in location 0,this pair is stored in location 1,

location 2,location 3,4,5 and 6. of array.To get the left child we

apply this formula 2i+1.So to get this guy’s left child in the array we replace 0

with ‘i’ so 2×0+1 so that’s 1 so this is left child and 2×0+2 so

this is right child.For 2’s left child we replace ‘i’ with 2 so 2×2+1 so that’s 5 and 2×2+2

so that’s 6 so thats it’s right child and to get a parent,for example to get

4’s parent in array we replace 4 with ‘i’ so (4-1)/2 so that’s 1. So 4’s parent is 1.So this is how

regular binary heap works.Now to support these 2 contains and decrease operation we need another map,we need another data

structure map to do that efficiently and in this map we are going to store this key. So every pair here is identified by this

key,unique value key and the second value here is just used to position them

in this binary heap.So now to check,so the way this map works is the key here

is this key and the value here is the position in the array.So ‘a’ is stored at

location 0, ‘b’ is stored at location 1, ‘c’ is stored at location 2 of array,’d’ is

stored at location 3,’e’ at 4,’f’ at 5 and ‘g’ at 6.So now to support contains operation what we do is we check does this heap

contains ‘c’ so all you have to do is go to this map and check does this map have a key ‘c’ and yes it does. So this can be done in a map in O(1)

time.What about decrease operation. So let’s say we have to decrease the

value of 5 to -2.So decrease this 5 to -2,this ‘F’

to -2.So what we do is we first come to this map,check where this ‘F’ is stored.So

‘F’ is stored at location 5,so we reach this point. Now we change the value here to be ‘F’ and -2.At this point it violates the property

of binary heap,minimum binary heap because this value is less than it’s parent. So using this formula (i-1)/2 so

(5-1)/2 so that’s 2 we,we check if this value is

less than this,it is so we’re gonna swap this data here. So here we get (F,-2) and here we have (C,6) and also

we have to go into this corresponding map and change their locations.So F’s new

location is 2 and C’s new location is 5.Now this ‘F’ is still violating this

property here because – 2 is less than -1 so again we’re gonna do a swap here. So (A,-1) is here and (F,-2) is here. So then,now our F’s new location is 0 and A’s

new location is 2. So this is how we support decrease key

operation in O(logn) time.So hopefully this helps you understand how we’re

going to use these 2 data structures combined together to have these 4

operations in the Prim’s algorithm. So in the next section let’s look at the

Prim’s Algorithm.The way this algorithm work is first we take all the vertices,put in this heap

plus map data structure which we just,just discussed with the value infinity and

the note the vertex from which we’re gonna start as a value 0.In this case we’re

gonna start from ‘A’ but we can start from any vertex.Then we’re gonna

explore neighbors of ‘A’,in this case ‘D’ and ‘B’ and check if they exist in this heap

plus map and if they do and if the value they are attached to is greater

than this edge weight then we update their values.So D,infinity so we update it to

1,A’s value is 3 so we update it to 3 and then we keep repeating this

process,then extractMin again and keep repeating this process until there are

elements in this heap plus map data structure.Also we’re going to store, we’re going to have another map

going from vertex to edge which is going to store for,for every vertex

which edge is contributing to the minimum value in this heap plus map data

structure. This is to get the final result and in

here we’re going to store the final result. So let’s do a traversal on this graph here.So

we start from ‘A’ we do an extract,we do an extractMin here so the minimum value is 0 so ‘A’ so ‘A’ comes

out of this heap plus map data structure. Then we’re going to explore neighbors of

‘A’.So first we go to ‘D’,so ‘D’ contains in this heap plus map and the value attached

with ‘D’ is infinity which is greater than 1 so we update this value to 1.And in

here we’re going to store this,say that ‘D’ is introduced,the minimum value for D

is coming from this edge (A,D).Then we’re gonna explore other neighbor of ‘A’ which is ‘B’.’B’

is in this map here and ‘B’,the minimum value of B is,the value attached with ‘B’ is

infinity which is greater than 3 so this value becomes 3 and we’ll indicate here

that ‘B’ is,B’s minimum value edge is coming from this edge (A,B).So as we

discussed heap plus map,the decrease operation can happen in O(logn)

time and contains operation can happen in O(1) time. So at this point we’ve done exploring all

the neighbours of ‘A’ so we’re done with ‘A’. And then we’re going to do extractMin on

this heap plus map which can again be done in

O(logn) time and get the next value.So the next min here is 1. So we’ll take 1 out and then we’re going to

check which edge contributed to this value 1 and to do that we come here and

see where,which edge contributed to that. So D’s (A,D) edge.So (A,D) will go into this final

result which has all the edges in the minimum spanning tree.Then we’re going

to remove this guy from here,from this heap plus map data structure and explore

its neighbours. So D’s 1st neighbour is 6 and ‘E’ is in

this heap plus map data structure,it is and the value attached to this guy is

greater than 6 so we replace this with 6 and we will say that ‘E’ is coming from (D,E). Then we’re gonna explore another

neighbor of ‘D’. So that’s ‘B’ and the value,’B’ is in

this heap plus map but the value with B is 3 is not less than this value 3 so we’re just going to ignore this edge

here and then we’re gonna look at the next neighbor of ‘D’ which is ‘C’.So ‘C’ is in this

heap plus map and the value of C is infinity which is greater than 1,so

we change this value to 1 and we’ll say that ‘C’ is coming from (D,C),edge (C,D).At this point

‘D’ is done exploring all its neighbors so we again go to this heap plus map and do

an extractMin here.So this time (C,1) comes out.So first thing we check is

where,who introduced this (C,1) into this heap plus map and that’s we go to this

vertex and that is (C,D).So (C,D) is also in final result and we’re gonna do extract

Min on this heap plus map.Now we’re gonna explore neighbours of ‘C’.So C’s first neighbour

we explore is ‘B’.Now the value stored with ‘B’ right now is 3. Well this edge has a weight 1 which is

less than 3 so this edge is better than what we have in here so we’ll change

this to 1 and we’ll say that B’s edge is (B,C). Then we’re going to explore other

neighbors of ‘C’,so that’s ‘D’.D’s not in this heap plus map data structure so

we’ll ignore ‘D’ and then we’re going to explore ‘F’.’F’ is there in this data structure and

the,and the value attached with ‘F’ is infinity which is the greater than 4 so

we’re going to replace this with 4. And we’re going to say that ‘F’ is coming

from this edge (C,F).They we’re gonna explore this neighbour ‘E’ and the value attached with ‘E’ right

now is 6 which is greater than this edge weight 5, so we’re going to replace this with 5

and then here we are going to say that ‘E’ is coming from (C,E) now.At this

point of time we’re done exploring all the neighbors of ‘C’,so we again go here

and do an extractMin. So this point,at this point we’re

going to extract ‘B’ out of this heap plus map and we’re gonna go and check which

edge introduced ‘B’ and that is (B,C). So (B,C) will go into the final

result and we’re gonna remove ‘B’ from this heap plus map data structure.

Now we’re gonna explore neighbors of ‘B’.So 1st we go to B’s ‘A’. It is not there in the c plus,heap plus

map data structure so we ignore it. It’s another neighbour is ‘D’.’D’ is also

not there so we ignore it,another neighbour is ‘C’ ‘C’ is also not there in this heap plus map.So we

ignore it as well.So now we move to the next,we’re gonna again do a extractMin on

this heap plus map.So next time we did is ‘F’ is 4.So 1st time we do is check

who introduced ‘F’ and that is edge (C,F).So (C,F) is also in final result and

we’ll remove (F,4) from here.So we’ll explore neighbours of ‘F’. So the 1st neighbor of ‘F’ is ‘C’ but ‘C’ is

not in this data structure so we ignore it and the next neighbour of ‘F’ is ‘E’ and the

value attached with ‘E’ here is 5 while this edge gets it done in 2 so replace this

5 with 2. And let’s say that ‘E’ is now coming from

(E,F) and then at this point of time we’re done exploring all the neighbours of ‘F’. So we go back here and we extract this last

guy out and we check who introduced this value 2. So that’s (E,F).So (E,F) is also in

final result. and we remove this guy from here and

we’ll look at its neighbours. So we go to ‘D’.’D’ doesn’t exist in this map,

in this data structure,’E’ doesn’t, ‘C’ doesn’t exist here and ‘F’ doesn’t

exist here.So we have totally done exploring ‘E’ at this point of time. So we go back here,at this point this heap

plus map data structure has no elements, it means that all the vertices have

been covered and we got our minimum spanning tree edges. So the edges

for this minimum spanning tree is this 1, this 1,this 1,this 4 and this 2. So let’s analyze the time and space

complexity.Space complexity is prettty straight forward.This,we are storing result,

we’re storing this map and we are storing heap plus map data structure.In the

worst case the space complexity will be E +V because we might have to store

all the edges of this graph. What about the time complexity? So we are

performing this operation on,so we’re performing so as

many edges we have we’re performing that operation that

many times on this heap plus map data structure.In the worst case the size of

this heap plus map data structure will be O(V), basically the size of the entire heap,

entire graph and we’re doing,in worst case ‘E’ operations on this thing and we

know that ‘contains’ work in O(1) time,extractMin works in O(logn)

time,add works in O(logn) time and decrease key works in O(logn)

time.So in worst case the time complexity will be O(Elog(V))

where ‘V’ is the size of this heap plus map data structure.So again the space

complexity is O(V+E) and then the time complexity will be O(Elog(V)).

So in the next section let’s look at that code for this algorithm.So the name of the

function is primMST.It takes in a graph and returns a list of edges which

form the minimum spanning tree. Let’s first initialize the data structure

which we’re going to use. So the first one is the binary min heap

which is the heap plus map data structure I discussed before. So if you want you can look at the class

to see how I’ve implemented it.Then the next data structure is a map from vertex

to edge,basically storing the edge which entered,which provided the

minimum value for this vertex in this min heap.And then finally this is a list

of edges which is just going to store the final result. So first thing we do is we iterate

through all the vertices in this graph and add them to the min heap with

the value, Integer.MAX_VALUE which is basically an infinity value and then

we randomly select start vertex from this graph and then decrease the weight

of that vertex in this min heap to 0. So basically this,this is the 1st

vertex which will get selected and then we go into this while loop until this

min heap has,is not empty. Then we select a vertex so then our

current will be the 1st,will be the minimum value vertex

in this min heap and then we check if this current has a

corresponding edge in this vertex to edge graph, map or not. So this will be missing for the start

vertex but it, this value should be available for every

other,other vertex so we check if the spanning tree edge is not null. If it is

not then we add it to the final result and then we are going to get every edge

for this,for this current vertex and then get the adjacent vertex for this

edge and then we’re going to check if this adjacent,adjacent vertex

exist in the min heap or not and if it does exist then is the weight attached

with this vertex greater than the edge weight or not.If both the

conditions are true basically if it exists in the min heap and the weight

attached,the current weight attached with this adjacent vertex is greater

than the edge weight then we’re going to go into the min heap and decrease the

value of that vertex to the current edge weight and then we’re going to add

this vertex and the edge into this vertex to

edge map and then we’re going to repeat the process for other edges of this

current vertex and once we are done totally exploring this vertex we’re going to go back and go to the top

and repeat the same process,basically again doing an extractMin for,

and getting another current vertex and then going through its neighbors and updating

the min heap. And finally the result will be stored

final result will be stored in this result list and we’ll just return this

list. So again the time complexity is O(E+V),

and space, time complexity is O(ElogV) and space

complexity is O(E+V).So this is all I’ve to talk

about Prim’s algorithm.Please like this video,share this video,comment on this

video,check out my facebook page facebook,facebook.com/tusharroy25

and check out my github link github.com/mission-peace/interview/wiki. Thanks again for watching this video.

Saving me in exam time… For placement preps it is very useful… do more videos as much you can… lol

I now type algo name Tushar Roy in Youtube search bar for my exams! ðŸ™‚ But plz see my doubts in your DP videos.

Thanks for the video, Awesome explanation

why unlike others,you didn't check edges already in set and upcoming edges makes cycle with it or not . is it different algo?

Appreciate your efforts!….great one…. ðŸ™‚

for those who came for details for min binaryheap from tushar's dijkstra algorithm video, watch from 1:15 to 5:55. cheers !

isn't the time complexity of contains operation in map is O(logN) ,how can it be O(1) ?

if we are implementing this in c++ then i think it would be better to use STL set instead of STL priority queue since when we gonna be updating the edge in the priority queue first we need to erase it and then insert it again and since priority queue doesn't have erase method but set has , it would be better to use set.

i am a novice, please correct me if i am wrong.

thanks a lot for your good explanation.

Fantastic Explanation! Best i have seen on youtube… Keep it up… Waiting for more uploads.. Thanks

excellent explanation, too bad that priority queues does not exist in C#

Is there any way to implement maps in C?

Your videos are really helpful. You got talent for this stuff.

Excellent explanation!

If you have created a LIST datastructure called FAN. Then add my name there ðŸ™‚

Sir, You are an excellent teacher and a wonderful person to help a lot of needy ones like me here. Thank u so much. Please keep up the good work!

perfectly explained!!..thank you

Instead of constructing BinaryMinHeap, can it be possible by using PriorityQueue?

Why would it use O(V + E) auxiliary space? Heap would have maximum V vertices and map would store only 1 edge per vertex(the edge with minimum path to that vertex).

You can really teach. Thank you for all your hard work. You're the exact opposite of all those professors clogging up the halls and offices at uni, because you can actually make this stuff easy to understand for human beings.

excellent explanation. thanks man

bro u are just awesome, keep it up , plz upload more videos

Amazing explanation ! ðŸ™‚

Your explanations of these graphing algorithms by far the the most thorough and clear. thank you so much for doing these.

You are really an amazing teacher.

Thanks a ton!! All your videos are extremely helpful ,especially before exams! Upload more videos as much as possible, you make things look so simple and easy.

This one is great

Tushar.. Do we really need resultList as the vertexToEdge map itself holds all the edges required for the result? Can the vertexToEdge map acts as the result set?

Nice explanation Tushar.. Thank you very much.

Excellent explanation! Keep it up. If 2 edges are found with same weight , which edge should I choose? After Step1, Can I choose edge BD instead of edge AB?

Thank you so much Tushar ðŸ™‚

Is heap+map and priority queue are same data structures??

then what is difference b/w prims and dijikstra both u explained same? u waste

Appreciate your efforts. Thank you for the video. It helped allot.

You are one of the best Data Structure teachers…………Far better than the ones in our college

It's faster to just trace the smallest immediate edge for a test. This is just what the algorithm has to do.

very nice….!!

mate because of you i could do one problem at university, thank you and good luck :-* (sorry for the bad english, not my native language)

Thanks man!!

At 2:07,I see why contains() is O(1).

But why is findMin() O(logN).Shouldnt it be O(1) since you can directly access the heap root in O(1).

Correct me if I am wrong.

You teach unbelievably well! Perfect!

aao na , mujhe chodo na !!

sir, please send me prims algorithm program in c

prims nd kruskal give same units answer

Thanks for the video. Can you provide the code of HeapMap in C++?

how does map takes O(1) in contains operation?

The source code on GitHub called primMST is missing a couple of class source code files such as Edge, Graph, and Vertex. Where are they?

Are you psychotic? Too much fast and your fucking indo-british pronunciation.

Algorithm starts @ 5:58

Does anyone know what text editor he is using for the code

shouldn't the decrease function work so that decrease(f,2) would subtract 2 from (f,7) and reposition it's location in the tree? so instead of repositioning (f,-2) as is in the video, it should reposition (f,5)?

I think your code will go into an infinite loop if the graph is disconnected. Nice explanation anyways, thanks.

Hi Tushar,Really loved the way you explained!!!In binary heap of ur code,i have a doubt,wen you update NodePosition map,y dont u update allNodes position.Because in few areas of your code you take node depending on postion from map.

Thankyou for the video!!

Can you please upload the link of how to construct heap + map datastructure in c++ . I am not able to find it.

shouldn't the extract min complexity be O(1) instead of O(logn)?

Why is the complexity not VlogV?

where is binary heap video on your channel? I dont find it anywhere in any of playlists .

I may be mistaken, but I think the operation while he's visiting C and replaces the AB edge of cost 3 with the BC edge of cost 1 is incorrect.

Again, I may be mistaken here, but I was under the impression you have to compare the cost of the edge (BC: 1) with the total cost to get to the edge from A (AD: 1 + CD: 1 = 2), or 2+1 = 3, and since 3 is not less than the current value stored, B's path to edge (AB: 3) is not overwritten.

I think what was done here in this specific case (just the CB edge, not the rest), was similar to how edges are selected for Kruscal's algorithm.

BC is still a valid edge of one of the MSTs of this particular graph, but what I'm saying is the reasoning of WHY the decision to replace AB with BC was incorrect under Prim's algorithm.

In other words, with his reasoning, if the edge BC was weighted 2, he would have still selected BC as the new edge to get to B from A, which would have resulted in a non-minimum spanning tree (ADCB: 1+1+2 = 4 vs AB: 3).

i don't like your talking style so don't talk hahaha

when do you insert things into the binary heap

what would be the cost of traversal for 9 or 10 as once a person has reached B node it need to return to C so that it could traverse further

As someone who doesn't use c++ for competitive, Tushar's java code is extremely useful ðŸ˜›

what happens when u try to extract min and there are two with the same value

Hi Tushar, hats off to you for investing so much of your time in this channel! This helps a lot of people!

THANK YOU !!!!!!!

Got it all in first time!

Could you explain why time complexity to check whether map contains a certain key how is O(1)??

How the vertices and edges of graph is used to construct Minimum Heap ?

too fast

can you please write complete implementation of priority queue with decrease key operation?

bhai aap great ho!!!!

actually sir the time complexity should be O(v^2logv)

Thank You for your videos Tushar..But can i request you to please speak a little slower?

Can you check if the formulae you had for children and parents were right? Coz. in Binay Heap this is how I implement it.

– Left child: 2 * i

– Right child: 2 * i + 1

– Parent: i / 2

Brilliant as usual.

Hello friends , By being a student of computer science student there are lots of videos related to particular topic. so to find which one is useful among them is difficult to find . so due to my channel i hope it will be easy for you to find the useful video by 1 click only. easy for you : https://www.youtube.com/channel/UCGXlUGE29uFvpsNUO7-gikQ To Subscribe :https://www.youtube.com/channel/UCGXlUGE29uFvpsNUO7-gikQ?sub_confirmation=1

Ty ðŸ˜€

Than you vary much for this video. You helped me a lot to understand this algorithm!

how edges are stored in graph?

Thank you so much Tushar!

Very well done – I appreciate your pacing throughout the lesson. You start the video building the foundation we need to then understand later parts of the lesson – that is key!

Hi,

I have one question

Instead of storing the edges in the result set can't we just print the values of hashmap at the end to print the result ,since the values will be overridden whenever there is an update of weight?

How can contains() be O(1) ? For unordered map, it's O(n) and for ordered one it's O(log n) (worst cases)

Sir Where can I find the Code for Prims Algorithm using C++ STL?

For source code in python: https://github.com/Sarthaks21/Graphs-Prims-Dijkstras

Shouldn't the order be ['AD', 'DC', 'CB', 'CF', 'FE'] where CD->DC ,BC->CB, EF->FE. he started with ( smallest element in dictioary+visited vertices) but later he changed the order. Correct me if i'm missing anything here

how does this algorithm avoid cycle?

Awesome!

Why does extract min takes O(logn) time ? We only need the first element of the heap, so shouldn't it be O(1) ?

how is contain operation take O(1) time? dont we have to traverse the whole map, hence it should take O(n) time?

can anyone please give the pseudocode for above method.

great exPL!

Thank you, Tushar. The explanation was nice and clear.

thnaks

you where talking a little faster than in your other videos, for me it was a little too fast, pls slow it down a bit next time

Really great explanations. Thanks!

Sir how can we impliment decrease key operation in priority queues in java …….as heaps can also be created using priorityqueue in java

WHY ARE YOU SHOUTING AT THE CAMERA

the ease and confidence in the voice adds clarity to the solution, i like it

In Binary Heap implementation, for node class he has used weight. Can anyone tell me what is the purpose of using weight attribute for node class ?

look at u r face in a mirror.! r u taking …drugw bro?!!!

Nice, I am confused why my other logic using Dijkstra's is not working and this is best explanation as least its showing right result. https://stackoverflow.com/a/25800210/1391499 I tried but not getting result and other in a book its written to use new d = weigh[x][v] + dist[v] {adj of x} and pass the new d with the priority queue and just add weight[x][v] to the distance array.