Studying for my data structures exam that is in... four hours. Your videos on Kruskals, Prims, and Dijkstra's are saving my life because I missed those lectures. Cheers mate!
One improvement I would make would be this: When choosing between two edges with the same weight, choose randomly between them, but give a probability weighted by the degree of the node you are connecting to. In many real life networks, nodes with high degree tend to receive more new nodes than less connected nodes.
You said that since you decided to pick the edge with amount 8 from B - C, you couldn't pick the edge amount with 8 also from A - H because it wasn't a part of the same tree. Why is that? I thought all of the vertices were in one tree? What is the criteria on that?
The reason why we can't choose a-h after choosing b-c is because it would form a cycle. Yet if we have chosen a-h instead of b-c, we would have a different resulting MST. You can have multiple MST from a single graph.
1. how does adding edge (b,h) with edge weight 11 form a cycle? 2. adding (c,i) and (g,f) with edge weight 2 is fine but adding (b,c) and (a,h) with edge weight 8 is a problem. can you elaborate?
1. with (b,h), it will loop the diagram. This means you will be creating a cycle where it goes from b, h, g, f, c, b. You do not want the arc/edge to be in a cycle (loop). Not connecting (b,h) means that there is no loop created. 2. Adding (c,i) and (g,f) is fine because they will not create a cycle, so you pick both. (b,c) and (a,h) is only a problem because you can not pick both as that will create a loop/cycle. But he states that you can pick either one as either (b,c) or (a,h) as there will sometimes be multiple minimum spanning trees (alternative paths).
if you also circle the vertices you've visited red, choosing the next edge/vertex pair will become easier without having to look through the entire graph to check for a cycle
so it means that the objective of this algorithm is to find the lowest edge-weights? and then it should start also in the lowest number of weights? thanks sir, btw you did a great job, i',m just a little bit confused because i don't know the rules of this algorithm.
well to find the minimum cost edges, which would eventually result mst. its a greedy algorithm, it doesn't necessarily start at the lowest number of weights but it will find them. and thank you sir
Given a graph G lets prove this by contradiction: G has two MST A,B. A has an edge e that B does not If we add that edge to B then there is a cycle. However, k. Algo would have picked the edge e0 over e therefore, A must not be in mst.
at a very high level, prims algorithms graph has to be connected, kruskals doesn't, in kruskals, you look at the next globally least costly edge where in prims you look at all edges from the current component to other vertices and find the smallest among them.
because the next two was the lowest costly edge, it doesn't matter how many of the same numbers you have, as long as it doesn't create a cycle, you can choose it.
![CAMPปลิ้น | EP.82[1/2] แก๊ง 3 สาวเพื่อนซี้บุก CAMPปลิ้นครั้งนี้ห้ามเสียอาการ](http://i.ytimg.com/vi/_6WUjXHe1TM/mqdefault.jpg)
bro just increase the thickness of the pen 😂😂
very good point
He did but the brush size stays the same 😭
Thanks for helping me with my hw, you rock my dude
I am glad I can help
"the main thing is, you can't have any psychos" - agree!
LOL........
I am latin and members of my family speak with an accent.
SCAM
He means *_cycles_*
Studying for my data structures exam that is in... four hours. Your videos on Kruskals, Prims, and Dijkstra's are saving my life because I missed those lectures. Cheers mate!
One improvement I would make would be this: When choosing between two edges with the same weight, choose randomly between them, but give a probability weighted by the degree of the node you are connecting to. In many real life networks, nodes with high degree tend to receive more new nodes than less connected nodes.
thank you very much, i have exam tomorrow
good luck!
so how did it go?
@@christoforoslapathiotis8064 some of lifes greatest mysteries. we may never know!
Pretty good@@christoforoslapathiotis8064
I thought it was my laptop's fan that sounds so loud when i listened to the audio. I panicked for a sec. But thanks! This really helped a lot!
Thank you for this!! (you have a nice voice though god)
You said that since you decided to pick the edge with amount 8 from B - C, you couldn't pick the edge amount with 8 also from A - H because it wasn't a part of the same tree. Why is that? I thought all of the vertices were in one tree? What is the criteria on that?
The reason why we can't choose a-h after choosing b-c is because it would form a cycle. Yet if we have chosen a-h instead of b-c, we would have a different resulting MST. You can have multiple MST from a single graph.
@@EducateYourselfNow Duh! Thank you!
Lifesaver
Again, short and simple to the point great video.
THIS VIDEO IS JUST 🔥🔥🔥🔥 THX A LOT MAN!!!!!
1. how does adding edge (b,h) with edge weight 11 form a cycle?
2. adding (c,i) and (g,f) with edge weight 2 is fine but adding (b,c) and (a,h) with edge weight 8 is a problem.
can you elaborate?
1. with (b,h), it will loop the diagram. This means you will be creating a cycle where it goes from b, h, g, f, c, b. You do not want the arc/edge to be in a cycle (loop). Not connecting (b,h) means that there is no loop created. 2. Adding (c,i) and (g,f) is fine because they will not create a cycle, so you pick both. (b,c) and (a,h) is only a problem because you can not pick both as that will create a loop/cycle. But he states that you can pick either one as either (b,c) or (a,h) as there will sometimes be multiple minimum spanning trees (alternative paths).
dope !!!!! thanks for this video. you just did 10 times better than my professor at cal state Monterey Bay
if you also circle the vertices you've visited red, choosing the next edge/vertex pair will become easier without having to look through the entire graph to check for a cycle
that is true, didn't think of that, thank you. i ll incorporate that in my upcoming videos
thats not correct. 3:00 would fail. you have to maintain a en.wikipedia.org/wiki/Disjoint-set_data_structure
so it means that the objective of this algorithm is to find the lowest edge-weights?
and then it should start also in the lowest number of weights?
thanks sir, btw you did a great job, i',m just a little bit confused because i don't know the rules of this algorithm.
well to find the minimum cost edges, which would eventually result mst. its a greedy algorithm, it doesn't necessarily start at the lowest number of weights but it will find them. and thank you sir
Nice explanation. Thank you.
I agree. Thank you so much for posting this video!
very nice explained video! Thank you
Thank you Andrei :)
Dude i love you man
thank you brother, i appreciate the love :)
i have exam tomorrow thanks man i got it
i hope you did well :)
THANKS FOR SAVING MY LIFE :D !!!!
I hate discreet mathmatcis
Hannah Lodge
U r explanation too gud...pls explain bellmanford algorithm also....
i will upload it soon
Given completely distinct edges in graph G, there is only a single MST.
Given a graph G lets prove this by contradiction:
G has two MST A,B.
A has an edge e that B does not
If we add that edge to B then there is a cycle.
However, k. Algo would have picked the edge e0 over e therefore, A must not be in mst.
thanks
what a king, ty
so whats difference btw prims
at a very high level, prims algorithms graph has to be connected, kruskals doesn't, in kruskals, you look at the next globally least costly edge where in prims you look at all edges from the current component to other vertices and find the smallest among them.
Thanks bro
Ok, how do we get the lowest weighted edges? How do we find if adding an edge would form a cycle? Isnt explaining this the point of these videos?
Nice work man :)
thank you :)
can anyone explain why did not we consider the other 8
we could, it wouldn't have mattered. I think i mentioned it in the video. 3:07
if he did it would form a loop abcfgha
either way forms a mst - mst is not necessarily unique
Can someone explain what he mains by cycle more?
thx bro
why did not you choose both edges with weight 8?
Can't understand about algorithm
well you could remove the c-d, and replace it with e-f. i think it will produce better MST
EE241C5A ftw!!!
thank you
the path you choose is not the shortest path
Is this the same as minimum cost arborescence?
Pretty nice, thanks.
thank you :)
How do you programmatically test if adding the edge will form a cycle?
how do you get those numbers?
if we have touched all the vertices but not all the edges yet what should i do? finish all the edges?
yes
It looks like C would form a cycle. Am I missing something?
there is no loop that encloses c
Good video, help me a lot
Thanks
good job
thank you!
Dikjstra algo??
Thank you so much! XD
How would choosing the edges "bh" create a cycle?
cycle would be : b c f g h, or b h g f c
THANK U SO MUCH FOR THIS
Awesome sir😍😍
BIG O!
Thank u sir
thanks a lot man its very helpful
answer is 42 ??
Isn't it 37?
@@marieselfer6621 i think its 37 too
why did you choose both the two
because the next two was the lowest costly edge, it doesn't matter how many of the same numbers you have, as long as it doesn't create a cycle, you can choose it.
thanks
But is it still minimal is the question.
In the Time Complexity part, you definitely gave a description of the runtime of the Prim's algorithm, not Kruskal's.
u such a copy ninja (from book introduction of algorithm)