For some reason I think this isn't just about mathematics. I feel like we can apply this algorithm into our lives! The last part of you wrapping up the concept that, "we can make the optimal choice available to us right now and not really worrying about future decision until we get there," resonates with me because we will end up with the 'correct' bigger picture which is proven by Kruskal! LOL. Jokes aside, thanks for making this video - now i got a good sense of this algorithm!
I would like to see a variance of this video adding the removal of snow on each house and man power on each not being necesarily the same and comencing from a particular house.
"Man power on each" is essentially the weight/number of people required I have no idea what you mean by "adding removing snow on each house" and "not being necesarily the same and comencing from a particular house"
@@timothychinye6008 sorry, english is my second language but I meant to say adding the removal of snow at each place. Pretty much like an snow removal crew going to each location to remove snow. However, this message was a bit old. I was able to figure it out thanks to this video anyways.
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.
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?
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.
It isn't. You're going for the smallest number route possible. If the road with a 6 existed, in order for the bottom left vertex to get to the top right vertex, they'd have to go +5, then +6. However, if you go the optimal way, you can just do +1, then +3. 4 is less than 11.
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.
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
Channel name checks out, I have never imagined I would say that in RUclips.
Really great explanation.
this video might save me from failing my math final tomorrow. I hope every day brings you joy king
Wow! Using real life example is the best teaching strategy.
Thank you very much.
For some reason I think this isn't just about mathematics. I feel like we can apply this algorithm into our lives! The last part of you wrapping up the concept that, "we can make the optimal choice available to us right now and not really worrying about future decision until we get there," resonates with me because we will end up with the 'correct' bigger picture which is proven by Kruskal! LOL. Jokes aside, thanks for making this video - now i got a good sense of this algorithm!
You are a very good teacher, thank you for the video!
The best explanation I have ever seen. Thank you!
this is like when the main protagonist says the name of the movie
Greatest 4th wall break
My favorite part of the video is where he says "It's minimal spanning time" and spans all over the place.
OMG the explanation is sooooo clear!
Thank you Brian!
This explanation is just too cool 😎😎😎😎
Great explanation video! Thank you!
fire vid keep posting, spanning tree!
I would like to see a variance of this video adding the removal of snow on each house and man power on each not being necesarily the same and comencing from a particular house.
"Man power on each" is essentially the weight/number of people required
I have no idea what you mean by "adding removing snow on each house" and "not being necesarily the same and comencing from a particular house"
@@timothychinye6008 sorry, english is my second language but I meant to say adding the removal of snow at each place. Pretty much like an snow removal crew going to each location to remove snow. However, this message was a bit old. I was able to figure it out thanks to this video anyways.
tnx now i got the proof
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.
Greatest video ever
Thanks great video
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
Thanks!
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.
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.
The more interesting example would be when some non-direct roads are optimal, instead of point-to-point connections.
How to practice?
This guy is fr trying to convince me that 6
Look at min 9:00 to 9:31
It isn't. You're going for the smallest number route possible.
If the road with a 6 existed, in order for the bottom left vertex to get to the top right vertex, they'd have to go +5, then +6.
However, if you go the optimal way, you can just do +1, then +3. 4 is less than 11.
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.
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.
Yoooo
Got lost
This explanation is just too cool 😎😎😎😎