Prim's Minimum Spanning Tree Algorithm | Graph Theory
ฝัง
- เผยแพร่เมื่อ 6 มิ.ย. 2024
- Prim's Minimum Spanning Tree Algorithm
Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on TH-cam:
www.udemy.com/course/graph-th...
Algorithms repository:
github.com/williamfiset/algor...
Video slides:
github.com/williamfiset/Algor...
Personal website:
www.williamfiset.com
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!!!
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.
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..
This helped me a lot. Many thanks to you, my friend
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
Thank you @WilliamFiset for such an amazing explanation, I wish you were teaching while I was still in college.
This deserves more views.
You're so good that i recommend your channel to every SWE i meet.
Very Nice Bro. Keep on making videos on other topics. Your animations are really usefull.
Excellent Explanation. It was crystal clear. I got everything in one go.
This helped me a lot! Thanks!
Clean and excellent explanation
Elegant & Beautiful
It's very helpful. Thanks
Thanks for the explanation!
Thanks William! Understood the algo :)
thank you so much !! Really helpful !
Simple and helpful ✌🏻
thank for your video ,it help me learn Tree algorithm !!!
brilliant explanation = thank you so much
Thanks williams
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 )
Thank you, Sir.
great job!!
Well done!
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?
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).
very helpful!
Thank you lots!!
Beautiful! :)
pls explain the time and space complexity as well
U'r the best man u'r the best
After watching people on the internet unnecessarily complicating this beautiful algorithm. I'm here!
Yes, Prims is nice.
Is each minimum-heavy spanning tree of N also a minimum spanning tree of N vertices!
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
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
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
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
I understand MST in 10 minutes while I spent long time in university book.
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?
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.