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.
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.
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.
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!
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_*
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.
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!
Thanks for helping me with my hw, you rock my dude
I am glad I can help
THIS VIDEO IS JUST 🔥🔥🔥🔥 THX A LOT MAN!!!!!
Nice explanation. Thank you.
I agree. Thank you so much for posting this video!
bro just increase the thickness of the pen 😂😂
very good point
He did but the brush size stays the same 😭
very nice explained video! Thank you
Thank you Andrei :)
Dude i love you man
thank you brother, i appreciate the love :)
THANKS FOR SAVING MY LIFE :D !!!!
THANK U SO MUCH FOR THIS
dope !!!!! thanks for this video. you just did 10 times better than my professor at cal state Monterey Bay
Lifesaver
what a king, ty
How do you programmatically test if adding the edge will form a cycle?
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
Good video, help me a lot
Nice work man :)
thank you :)
Awesome sir😍😍
Thanks bro
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
Thanks
Thank you so much! XD
Pretty nice, thanks.
thank you :)
the path you choose is not the shortest path
thx bro
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).
Is this the same as minimum cost arborescence?
how do you get those numbers?
Thank you for this!! (you have a nice voice though god)
thanks
Thank u sir
if we have touched all the vertices but not all the edges yet what should i do? finish all the edges?
yes
U r explanation too gud...pls explain bellmanford algorithm also....
i will upload it soon
i have exam tomorrow thanks man i got it
i hope you did well :)
good job
thank you!
why did not you choose both edges with weight 8?
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?
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?
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.
Dikjstra algo??
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.
EE241C5A ftw!!!
BIG O!
well you could remove the c-d, and replace it with e-f. i think it will produce better MST
thanks a lot man its very helpful
answer is 42 ??
Isn't it 37?
@@marieselfer6621 i think its 37 too
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
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.
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.
Can't understand about algorithm
u such a copy ninja (from book introduction of algorithm)
I hate discreet mathmatcis