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.
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
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).
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.
When I get my degree after next semester, I'll raise a cheers to you for helping me get through algorithms!
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!
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.
Again, short and simple to the point great video.
"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_*
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
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
dope !!!!! thanks for this video. you just did 10 times better than my professor at cal state Monterey Bay
bro just increase the thickness of the pen 😂😂
very good point
He did but the brush size stays the same 😭
Nice explanation. Thank you.
I agree. Thank you so much for posting this video!
Thanks for helping me with my hw, you rock my dude
I am glad I can help
very nice explained video! Thank you
Thank you Andrei :)
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!
thank you man! i finally understand it
very nice explanation
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).
i have exam tomorrow thanks man i got it
i hope you did well :)
Thank you for this!! (you have a nice voice though god)
U r explanation too gud...pls explain bellmanford algorithm also....
i will upload it soon
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
if we have touched all the vertices but not all the edges yet what should i do? finish all the edges?
yes
No.
How do you programmatically test if adding the edge will form a cycle?
the path you choose is not the shortest path
Awesome sir😍😍
Nice work man :)
thank you :)
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.
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
Good video, help me a lot
How would choosing the edges "bh" create a cycle?
cycle would be : b c f g h, or b h g f c
Can someone explain what he mains by cycle more?
good job
thank you!
Dude i love you man
thank you brother, i appreciate the love :)
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?
what a king, ty
Lifesaver
Is this the same as minimum cost arborescence?
how do you get those numbers?
THANKS FOR SAVING MY LIFE :D !!!!
Pretty nice, thanks.
thank you :)
thanks a lot man its very helpful
answer is 42 ??
Isn't it 37?
@@marieselfer6621 i think its 37 too
@@Brrrzna291 Maybe another spanning tree would get a lower total cost than 37?
why did not you choose both edges with weight 8?
THANK U SO MUCH FOR THIS
It looks like C would form a cycle. Am I missing something?
there is no loop that encloses c
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
Thanks bro
Dikjstra algo??
thank you
BIG O!
well you could remove the c-d, and replace it with e-f. i think it will produce better MST
Thank you so much! XD
Thank u sir
In the Time Complexity part, you definitely gave a description of the runtime of the Prim's algorithm, not Kruskal's.
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.
@@niklaspeura4193 Yes, why would this give a minimal spanning tree?
thx bro
EE241C5A ftw!!!
Thanks
Hannah Lodge
Can't understand about algorithm
u such a copy ninja (from book introduction of algorithm)
I hate discreet mathmatcis