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!
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.
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.
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.
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.
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).
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!!!!
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.
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
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, 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?
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
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.
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)?
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.
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).
+Lionel Messi a MAP is used to speed up that operation at the cost of space. MAP stores key => position , HEAP is implemented using an ARRAY, meaning, it takes almost O(1) (depending on the quality of your HASH FUNCTION) to find an element (and thus the position in the ARRAY), from there is O(1) to get the element from the HEAP since you already now its position. This implementation achieves good speed at the cost of waisting a los of space: Graph (adjacency list): O(V+E) Heap (array) = O(V) + Map (HashTable) = O(V) MST List of Edges = ~O(V) MST Map = ~O(V) As you can see, for a 40MB graph we are looking at a very expensive implementation in terms of memory allocation. Time also gets a huge hit on performance. Think of it this way: it is not the same looking for a shoe in a house than looking for it in a Football stadium. Now, since he is using java, think of the garbage collections (which are blocking calls). If you use a lot of space it will be reclaimed sooner or later (most likely sooner). All in all, time complexity is very relative when you do not understand the big picture.
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.
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.
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()
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.
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
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!
Your implementation does not give a MST for the following example. Every time you add a vertex (using min heap), your algorithm does a BFS only on one vertex. But instead, you should do a BFS on all the vertices of the intermediate MST. For e.g. if AB = 2 (instead of 3), BD = 4 (instead of 3) and DC = 3 (instead of 1), your implementation would still give the same result which is AD, CD, BC, CF, FE (length = 11). However, the correct solution is AD, AB, BC, CF, FE (length = 10) which is the MST.
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.