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.
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!
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.
from the last 7 days was stuck with a particular doubt. Was losing my mind over it! 7 mins into the video and my doubt is cleared. Thank you so much. May the Gods bless you.
Neat, clear and thorough presentation. I am certain that you are helping a good chunk of students who do not get enough from their professors' lectures. Thank you and keep up the good work (y).
+Tushar Roy btw Tushar, it would be very helpful if you could do tutorials on sorting algorithms, especially the advanced ones such as quicksort, mergesort, shellsort.
Hey man. Yours are some of the best and simplest videos for these weirdly complex data structures. Keep up the good work. Also, as you are handling complex stuff, could you start making videos for different complex Dynamic Problem? It will be a great help.
Hi Tushar, Thanks so much for your videos. Keep these videos coming. It helped in understanding algorithms so well. I used to spent lot of time to understand algorithms but your videos helped me in understanding in less than 20 mins. Thanks so much for the videos. I did feel you are talking a little faster but i changed the video playback speed :) Cheers!!!!
Thanks for the great explanation. One point which is not mentioned in the video is that this is eager implementation of Prim's algorithm. There exists a lazy implementation of prim's algorithm with a different implementation. However, the basic idea remains the same.
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?
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?
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.
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).
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).
somebody please explain this. I was thinking the same thing Heap has at most V space , map would be same thing. In the arraylist where you store the minimum edge that contributes the vertex that is V space as well and the answer array is at most V space as well right? because it's a minimum spanning tree so you're only going to have the number of edges needed to connect all the vertices which can't be more than the number of vertices so V again...so 4V in total so O(V) space seems correct. Somebody tell me why I'm wrong
It's because you have to store the weights some how and the only way to do so efficiently is to generate a hashmap of each weight. Also you would need to keep track of the connectivity (adjacency) list of each node so doing which basically outlines all edges.
Tushar Roy your video is great! i learned a lot! but i have a question. why is the time complexity for the heap 'contains' operation O(1)? i guess we need to loop through all the map and check if 'B' contain in the map... is not that O(n)? thanks
btw do you know how to solve traveling sales men with branch and bound? thanks i know how to solve it by dp but it take too many space if i have 25 cities . thanks a lot!
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?
A graph can have more than one minimum spanning tree. So, while traversing in the graph if you will find two edges of same weight then you can choose either first one or second one. Output will result in two different minimum spanning tree.
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)?
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.
Should use D-ary heap instead of Binary heap w/ Prim's MST algo. D is tree order (i.e. max # of children of any node). D=log2(V) (D=E/V is another way, but log2(V) gives better performance). removemin and decrease are the 2 prominent OPs among which decrease is more frequent (O(E), removemin at O(V)). decrease causes swim whereas removemin causes sink. swim causes comparison b/w a node with it's parent, all the way till the root if required, whereas sink causes getting the smallest among all children and comparing that with the node, all the way till final level if required. So swim performs better with D-ary heap whereas sink performs better with binary heap. But since swims are more frequent than sinks, D-ary heap has to be used with D=log2(V) to strike a balance in the performance of sinks and swims. sink and swim run in O(log2(V)) time with binary heap. With D-ary heap they run in O(log(V)) time =~ O(log(V)) time
Thank you boss! You are good. what if i want an interface to display the graph, as input and the output will also be displayed in form of graph (to solve general problems) with each of the iterations (with table displayed). How can this be implemented using java. Thank you
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
His formulae are right. So are yours. It's because he started the index of root node at 0 and you started it at 1. The formulae depend on how you index.
Hey Tushar, At any points we are only storing V vertices and V edges. So space complexity is O(V) not O(E+V). Think and you will realise. Ps- We are always storing V edges and never storing E edges. |E| can be O(V) in special cases but still space complexity remains O(V+E) = O(V). For |E| of order O(V^2) we are only storing V edges, so space complexity remains to be O(V). Give it a thought, and you will get it. Map of result has V keys, Heap + Map will have at most V nodes, and result list will have V-1 edges. Its all V edges + V vertices.
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
Thank you very much sir for your tutorials,the way you explain is really nice but i request you to suggest me source from where i should study java so that i can be able to implement these graphs logic using predefined function P.S-I know collection framework,but not method such as getAllVertexForEdge()
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.
I see where I went wrong. For anyone having the same doubt,peeking the min value i.e just reading the min value takes O(1). But in extractMin(),the min element is not only read but also removed from the heap,so readjusting the links in heap takes O(logN).
After extracting minimum element, it disturbs the property of minimum heap. So we have to call heapify function which takes O(logn) time to convert it into minimum heap.
![[LIVE] : ONE ลุมพินี 68 | คู่เอก "พระจันทร์ฉาย vs โจนาธาน"](http://i.ytimg.com/vi/F3IM3w-XchI/mqdefault.jpg)
for those who came for details for min binaryheap from tushar's dijkstra algorithm video, watch from 1:15 to 5:55. cheers !
Now this is some helping out!!!
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.
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!
Your explanations of these graphing algorithms by far the the most thorough and clear. thank you so much for doing these.
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.
the ease and confidence in the voice adds clarity to the solution, i like it
You are the boss ! I simply love your tutes !
Hi Tushar, hats off to you for investing so much of your time in this channel! This helps a lot of people!
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!
Thanks for the video, Awesome explanation
from the last 7 days was stuck with a particular doubt. Was losing my mind over it!
7 mins into the video and my doubt is cleared.
Thank you so much. May the Gods bless you.
Your tutorials and explanations are awesome, keep it up!
You teach unbelievably well! Perfect!
Thank you, Tushar. The explanation was nice and clear.
Neat, clear and thorough presentation. I am certain that you are helping a good chunk of students who do not get enough from their professors' lectures. Thank you and keep up the good work (y).
+Tushar Roy btw Tushar, it would be very helpful if you could do tutorials on sorting algorithms, especially the advanced ones such as quicksort, mergesort, shellsort.
Your videos are really helpful. You got talent for this stuff.
Appreciate your efforts. Thank you for the video. It helped allot.
Fantastic Explanation! Best i have seen on youtube... Keep it up... Waiting for more uploads.. Thanks
Appreciate your efforts!....great one.... :)
Hey man. Yours are some of the best and simplest videos for these weirdly complex data structures. Keep up the good work. Also, as you are handling complex stuff, could you start making videos for different complex Dynamic Problem? It will be a great help.
You are one of the best Data Structure teachers............Far better than the ones in our college
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)
Than you vary much for this video. You helped me a lot to understand this algorithm!
Really great explanations. Thanks!
Thank you so much Tushar!
Great videos ! Thanks for the explanations !
Thank u sir for all u'r videos we are getting so much of knowledge about the subject.i want skip list information,
program.
You are really an amazing teacher.
Hi Tushar,
Thanks so much for your videos. Keep these videos coming. It helped in understanding algorithms so well. I used to spent lot of time to understand algorithms but your videos helped me in understanding in less than 20 mins. Thanks so much for the videos. I did feel you are talking a little faster but i changed the video playback speed :) Cheers!!!!
Very very clear, Oh you do a great job!
Nice explanation Tushar.. Thank you very much.
Thank you so much Tushar :)
THANK YOU !!!!!!!
Got it all in first time!
perfectly explained!!..thank you
Brilliant as usual.
Saving me in exam time... For placement preps it is very useful... do more videos as much you can... lol
Amazing explanation ! :)
Thanks for the great explanation. One point which is not mentioned in the video is that this is eager implementation of Prim's algorithm. There exists a lazy implementation of prim's algorithm with a different implementation. However, the basic idea remains the same.
Thanks ..
best lecture representation..!
@Tushar It looks like the space complexity should be O(V) as we're only going to store a single edge per vertex, did I miss anything?
thanks a lot for your good explanation.
bro u are just awesome, keep it up , plz upload more videos
Hi! Really enjoyed your tutorial. Would be great if you could upload videos on graph colouring problems.
your tutorials are pretty good :) please upload your tutorials on Number theory :)
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?
Great lesson
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
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?
bhai aap great ho!!!!
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.
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).
Thanks man!!
I now type algo name Tushar Roy in TH-cam search bar for my exams! :) But plz see my doubts in your DP videos.
where is binary heap video on your channel? I dont find it anywhere in any of playlists .
oky thank you and if we are simply given a que to solve a spanning tree which is directed ..so which method to use ?
As someone who doesn't use c++ for competitive, Tushar's java code is extremely useful :P
This one is great
nice explanation
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.
It's faster to just trace the smallest immediate edge for a test. This is just what the algorithm has to do.
no
Awesome!
what happens when u try to extract min and there are two with the same value
when do you insert things into the binary heap
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).
somebody please explain this.
I was thinking the same thing Heap has at most V space , map would be same thing. In the arraylist where you store the minimum edge that contributes the vertex that is V space as well and the answer array is at most V space as well right? because it's a minimum spanning tree so you're only going to have the number of edges needed to connect all the vertices which can't be more than the number of vertices so V again...so 4V in total so O(V) space seems correct.
Somebody tell me why I'm wrong
It's because you have to store the weights some how and the only way to do so efficiently is to generate a hashmap of each weight. Also you would need to keep track of the connectivity (adjacency) list of each node so doing which basically outlines all edges.
Tushar Roy
your video is great! i learned a lot! but i have a question. why is the time complexity for the heap 'contains' operation O(1)? i guess we need to loop through all the map and check if 'B' contain in the map... is not that O(n)? thanks
thanks~
btw do you know how to solve traveling sales men with branch and bound? thanks i know how to solve it by dp but it take too many space if i have 25 cities . thanks a lot!
How the vertices and edges of graph is used to construct Minimum Heap ?
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?
A graph can have more than one minimum spanning tree. So, while traversing in the graph if you will find two edges of same weight then you can choose either first one or second one. Output will result in two different minimum spanning tree.
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)?
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.
very nice....!!
Should use D-ary heap instead of Binary heap w/ Prim's MST algo. D is tree order (i.e. max # of children of any node). D=log2(V) (D=E/V is another way, but log2(V) gives better performance). removemin and decrease are the 2 prominent OPs among which decrease is more frequent (O(E), removemin at O(V)). decrease causes swim whereas removemin causes sink. swim causes comparison b/w a node with it's parent, all the way till the root if required, whereas sink causes getting the smallest among all children and comparing that with the node, all the way till final level if required. So swim performs better with D-ary heap whereas sink performs better with binary heap. But since swims are more frequent than sinks, D-ary heap has to be used with D=log2(V) to strike a balance in the performance of sinks and swims. sink and swim run in O(log2(V)) time with binary heap. With D-ary heap they run in O(log(V)) time =~ O(log(V)) time
is the process same for directed graphs?
Thank you boss! You are good. what if i want an interface to display the graph, as input and the output will also be displayed in form of graph (to solve general problems) with each of the iterations (with table displayed). How can this be implemented using java. Thank you
Is there any way to implement maps in C?
why unlike others,you didn't check edges already in set and upcoming edges makes cycle with it or not . is it different algo?
sorry, i got confused with kruskal algorithm for same.
Nice explenation. I think kruskal algorithem for MST is way simpler.
Sir how can we impliment decrease key operation in priority queues in java .......as heaps can also be created using priorityqueue in java
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
His formulae are right. So are yours. It's because he started the index of root node at 0 and you started it at 1. The formulae depend on how you index.
Sir Where can I find the Code for Prims Algorithm using C++ STL?
Ty :D
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?
here it is- github.com/mission-peace/interview/blob/master/src/com/interview/graph/Graph.java
mast..
Why do you extract F after B is all checked?
Hey Tushar, At any points we are only storing V vertices and V edges. So space complexity is O(V) not O(E+V). Think and you will realise. Ps- We are always storing V edges and never storing E edges. |E| can be O(V) in special cases but still space complexity remains O(V+E) = O(V). For |E| of order O(V^2) we are only storing V edges, so space complexity remains to be O(V). Give it a thought, and you will get it. Map of result has V keys, Heap + Map will have at most V nodes, and result list will have V-1 edges. Its all V edges + V vertices.
how does this algorithm avoid cycle?
how edges are stored in graph?
can you please write complete implementation of priority queue with decrease key operation?
Thanks for the video. Can you provide the code of HeapMap in C++?
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
I love you bro.
Does anyone know what text editor he is using for the code
Thank you very much sir for your tutorials,the way you explain is really nice but i request you to suggest me source from where i should study java so that i can be able to implement these graphs logic using predefined function
P.S-I know collection framework,but not method such as getAllVertexForEdge()
I thought those are predefined method and i don't know.well,thank you very much sir
+Rahul Raja use JgraphT library
great exPL!
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.
I see where I went wrong.
For anyone having the same doubt,peeking the min value i.e just reading the min value takes O(1).
But in extractMin(),the min element is not only read but also removed from the heap,so readjusting the links in heap takes O(logN).
how is contain operation take O(1) time? dont we have to traverse the whole map, hence it should take O(n) time?
we can maintain a map for the contain operation..hence it will take O(1) time.
Could you explain why time complexity to check whether map contains a certain key how is O(1)??
can someone help me with this?
The ADT in use is called a hash table. This video should help: th-cam.com/video/Ke_tII6Y0GE/w-d-xo.html
thankuuuuuuuu
Why does extract min takes O(logn) time ? We only need the first element of the heap, so shouldn't it be O(1) ?
After extracting minimum element, it disturbs the property of minimum heap. So we have to call heapify function which takes O(logn) time to convert it into minimum heap.
@@MrRounaksoni yup, got it. Thanx bro :)
Instead of constructing BinaryMinHeap, can it be possible by using PriorityQueue?
Yes..but priorityq is best implemented by heap
Good question. But BinaryMinHeap is a combination of heap and map implementation which cannot be achieved using priorityQueue.
Why is the complexity not VlogV?