This explanation is so good! Understanding this algorithm is already hard, and coding the solution up is difficult on another level. I tried reading the code on different websites and in different videos, and I had a hard time understanding it. However, you example, visualization and clean code made me understand everything in less than 20 minutes. Thank you so much!!!
3:27 to be more precise, the two versions (lazy and eager) have the same complexity of O(E*log V) because log(E) = O(log(V)). This is because E < V^2, so log(E) < log(V^2) = 2*log(V) = O(log V). In big-O notation, it never really makes sense to use log(E) instead of log(V) for graph algorithms.
How will the complexity be E log E ? Is it for Adj list representation because for a matrix representation I am selecting a vertex then looping through all other vertices to add them in the queue, if an edge exists at all so I am doing the work V times right? So the complexity will still be O(V^2 )
Hey awsome video but I don't understand what happens at 8:41 you say its stale because (2,1,3) but how did you get that should'n it have been (1,2,3) because you were starting from node 1?
For someone in doubt like myself, wondering which node to start from to put into priorityqueue, you can start with nay node and will still get the same MINIMUM SPANNING TREE (which by definition contains all nodes joined via the minimum weighted edges)
Why choose vertex which is connected by minimum adge? it works even if we traverse and choose vertex from an ordinary queue(not priority queue) Becoz the goal is to connect vertex with minimum edge only and we can archive this even by choosing elements randomly
@@WilliamFiset-videos Hey. What would happen if i had a node with 2 Edges. The first one has a cost of 0 and the second a cost of 2. I follow the Edge with cost 0 and end up at a Node with another 2 Edges which all have higher edge costs than 2. If i dequeue i'd get the Edge from the first Element with cost 2 right? Would that change anything in the workflow?
@@ikaros9727 You need to get to ALL the nodes in the graph anyway, so the workflow doesn't change. You always choose the cheapest edge and follow it to get the minimum spanning tree.
Thank you so much!!! learning algorithms from a book in the university is really hard and your videos are super helpful!!
don't use my display picture please
@@mechy6065 Is this a coincidence?? LOL
@Kohen Kaden hmmmmmmmm
exactly the same
This explanation is so good! Understanding this algorithm is already hard, and coding the solution up is difficult on another level. I tried reading the code on different websites and in different videos, and I had a hard time understanding it. However, you example, visualization and clean code made me understand everything in less than 20 minutes. Thank you so much!!!
Better explanation than Leetcode premium, thanks a lot!
I'm so glad I found your channel! Thank you so much for your hard work!
Hands down best channel for graph algorithms resource on youtube. Thanks mate
Nope, Hands Up, You are under arrest😂😂 For saying the Truth..
I have missed these videos so much. Awesome explanation.
Thanks for making it super easy to understand. I am super lucky that I found your channel among the pile.
This deserves more views.
You're so good that i recommend your channel to every SWE i meet.
This helped me a lot. Many thanks to you, my friend
Excellent Explanation. It was crystal clear. I got everything in one go.
Thank you @WilliamFiset for such an amazing explanation, I wish you were teaching while I was still in college.
brilliant explanation = thank you so much
Clean and excellent explanation
Elegant & Beautiful
thank for your video ,it help me learn Tree algorithm !!!
Very Nice Bro. Keep on making videos on other topics. Your animations are really usefull.
This helped me a lot! Thanks!
Simple and helpful ✌🏻
Thanks William! Understood the algo :)
Thanks williams
3:27 to be more precise, the two versions (lazy and eager) have the same complexity of O(E*log V) because log(E) = O(log(V)). This is because E < V^2, so log(E) < log(V^2) = 2*log(V) = O(log V). In big-O notation, it never really makes sense to use log(E) instead of log(V) for graph algorithms.
What about when there are O(V^2) edges? For example a dense or complete graph.
@@amey7064 then both are O(V^2 log V).
It's very helpful. Thanks
How will the complexity be E log E ? Is it for Adj list representation because for a matrix representation I am selecting a vertex then looping through all other vertices to add them in the queue, if an edge exists at all so I am doing the work V times right?
So the complexity will still be O(V^2 )
After watching people on the internet unnecessarily complicating this beautiful algorithm. I'm here!
thank you so much !! Really helpful !
Thanks for the explanation!
Thank you lots!!
Well done!
great job!!
Beautiful! :)
pls explain the time and space complexity as well
Thank you, Sir.
Hey awsome video but I don't understand what happens at 8:41 you say its stale because (2,1,3) but how did you get that should'n it have been (1,2,3) because you were starting from node 1?
very helpful!
U'r the best man u'r the best
For someone in doubt like myself, wondering which node to start from to put into priorityqueue, you can start with nay node and will still get the same MINIMUM SPANNING TREE (which by definition contains all nodes joined via the minimum weighted edges)
Jatin Shashoo that’s right, except there may be multiple spanning trees
yes, and all the trees weight cost the same
Why choose vertex which is connected by minimum adge? it works even if we traverse and choose vertex from an ordinary queue(not priority queue)
Becoz the goal is to connect vertex with minimum edge only and we can archive this even by choosing elements randomly
Do you know what the scariest think in the world is >??
No, and I don't even know how to reverse a linked list.
not knowing how to invert a binary tree?
Yes, Prims is nice.
what does to poll mean? we just choose a node randomly?
Polling is the act of removing a node from the top of the priority queue. In the pseudocode in this video it's the equivalent of .dequeue()
@@WilliamFiset-videos I see thank you
Is each minimum-heavy spanning tree of N also a minimum spanning tree of N vertices!
where in the code do we select the cheapest edge from the PQ?
That's the line 'edge = pq.dequeue' at 13:14 which removes the next best edge from the priority queue.
@@WilliamFiset-videos Hey. What would happen if i had a node with 2 Edges. The first one has a cost of 0 and the second a cost of 2. I follow the Edge with cost 0 and end up at a Node with another 2 Edges which all have higher edge costs than 2. If i dequeue i'd get the Edge from the first Element with cost 2 right? Would that change anything in the workflow?
@@ikaros9727 You need to get to ALL the nodes in the graph anyway, so the workflow doesn't change. You always choose the cheapest edge and follow it to get the minimum spanning tree.
the pq sorts based on the minimum edge cost,so it always dequeue the minimum edge
I understand MST in 10 minutes while I spent long time in university book.
why am i hearing "oh hell nah" in the background 5:20
damn I thought 2:14 was about to be a swastika
2:12 when i started doing it, it looked kinda sus bro hahahaha
almost a nazi sign
One minor thing: it seems mstEdges[0] stays null.