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.
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
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).
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!
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!
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!
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.
"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_*
Again, short and simple to the point great video.
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
dope !!!!! thanks for this video. you just did 10 times better than my professor at cal state Monterey Bay
Thanks for helping me with my hw, you rock my dude
I am glad I can help
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
THIS VIDEO IS JUST 🔥🔥🔥🔥 THX A LOT MAN!!!!!
thank you man! i finally understand it
very nice explanation
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!
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 :)
what a king, ty
very nice explained video! Thank you
Thank you Andrei :)
Nice work man :)
thank you :)
THANKS FOR SAVING MY LIFE :D !!!!
Good video, help me a lot
Thank you for this!! (you have a nice voice though god)
Lifesaver
Awesome sir😍😍
U r explanation too gud...pls explain bellmanford algorithm also....
i will upload it soon
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 U SO MUCH FOR THIS
the path you choose is not the shortest path
Pretty nice, thanks.
thank you :)
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
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).
good job
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.
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?
why did not you choose both edges with weight 8?
thank you
Thanks bro
Is this the same as minimum cost arborescence?
Thank you so much! XD
thanks
Can someone explain what he mains by cycle more?
How do you programmatically test if adding the edge will form a cycle?
if we have touched all the vertices but not all the edges yet what should i do? finish all the edges?
yes
No.
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
thx bro
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?
Thanks
Dikjstra algo??
how do you get those numbers?
It looks like C would form a cycle. Am I missing something?
there is no loop that encloses c
In the Time Complexity part, you definitely gave a description of the runtime of the Prim's algorithm, not Kruskal's.
Thank u sir
How would choosing the edges "bh" create a cycle?
cycle would be : b c f g h, or b h g f c
well you could remove the c-d, and replace it with e-f. i think it will produce better MST
BIG O!
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.
EE241C5A ftw!!!
Can't understand about algorithm
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?
I hate discreet mathmatcis
u such a copy ninja (from book introduction of algorithm)