How Do You Calculate a Minimum Spanning Tree?
Vložit
- čas přidán 19. 06. 2024
- A story based on Kruskal's Algorithm
***
This video is part of a project I worked on in graduate school for Professor Karen Brennan's beautiful course T550: Designing for Learning by Creating. Spanning Tree is now an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
Channel name checks out, I have never imagined I would say that in CZcams.
Really great explanation.
Wow! Using real life example is the best teaching strategy.
Thank you very much.
You are a very good teacher, thank you for the video!
Great explanation video! Thank you!
OMG the explanation is sooooo clear!
Thank you Brian!
Thanks great video
This explanation is just too cool 😎😎😎😎
fire vid keep posting, spanning tree!
I would like to see a variance of this video adding removing snow on each house and man power on each not being necesarily the same and comencing from a particular house.
Thanks!
Greatest video ever
tnx now i got the proof
this is like when the main protagonist says the name of the movie
Greatest 4th wall break
This sounds so much like a variation of Dijkstra... am I wrong?
yes, you are wrong.
@@xiangli9588 thanks for the clarity and info packed response.
@@qwarlockz8017 but prim's algorithm is very similar to dijkstra
They are quite different. Kruskal's algorithm is used to find the minimum cost spanning tree, as depicted in the video, but Dijkstra is used in path finding from a given node in a graph, such that the result you get from dijkstra is the minimum distance and path required to reach all other nodes from a particular node.
They are similar in that the greedy or locally optimum solution ends up yielding the globally optimum solution. They are also similar in that they add/follow the cheapest edge of all valid choices in each iteration.
Wouldn't a way to ensure maximum efficiency be first to check if any nodes only have one edge and if so connect those edges first thefore removing that edge from any future comparisons and lowering the number of connections needed to reach n-1 nodes once you start the algorithm?
Not from an algorithmical standpoint. Since you'll need to account for those specific roads either way the only difference you introduce is when you account for them. And since you need to look them up separatly in your version you will need to look at all houses first to check if they have one connection. So you'll check houses which don't have only one connection in this step and then once again when you check them for the minimal weight path there.
From conceptual perspective it's useful to reduce problem
Excuse me broher, but I didn't get the cut property. If you take the 3-weight road and then the 6-weigth road, you will end up needing 19 volunteers rather than 18. But you mention that according to this property, you will end up still with a subset of a minimal spannin tree. Could you explain me further please?
Look at minute 9:00 to 9:32
This guy is fr trying to convince me that 6
Look at min 9:00 to 9:31
The more interesting example would be when some non-direct roads are optimal, instead of point-to-point connections.
Wait, do the roads need to be cleared for people to travel to the blocked roads?
Yes.
They start clearing the road they can get to before getting to the others.
How to practice?
what if two edges have the same weight?
You go with both! Unless one of them creates a loop, then you skip it. If one would create a loop if the other is chosen, either is fine
A loop is a path that starts and ends from the same place, ie the path 4-2-1 in the diagram in the video
@@ferusskywalker9167 oh, makes sense, going with both is kind of the same as going with one and then the other, in no specific order, and if taking both makes a loop, than taking either has the same effect on the total connections. Thanks.
1. Connect a house to the other.
2. Take any two houses and connect them if one and only one has not connected.
3. Repeat 2.
Got lost
This explanation is just too cool 😎😎😎😎