Kruskal's Algorithm: Minimum Spanning Tree (MST)

Example of Kruskal's algorithm

[@countchungalitus7604]

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!

[@monaami555]

"the main thing is, you can't have any psychos" - agree!

[@hdjksa52]

LOL........ I am latin and members of my family speak with an accent.

[@user-rf4vc7mt4d]

SCAM

[@amrahmed7856]

He means *_cycles_*

[@Alkis05]

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.

[@dedel0810]

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!

[@MuhidAbid14point75]

Again, short and simple to the point great video.

[@jacopomaccari4086]

bro just increase the thickness of the pen 😂😂

[@EducateYourselfNow]

very good point

[@anoriginalnick]

He did but the brush size stays the same 😭

[@tamersahin5189]

THIS VIDEO IS JUST 🔥🔥🔥🔥 THX A LOT MAN!!!!!

[@gongjiaji2489]

thank you very much, i have exam tomorrow

[@EducateYourselfNow]

good luck!

[@christoforoslapathiotis8064]

so how did it go?

[@sakethcherukuri277]

@@christoforoslapathiotis8064 some of lifes greatest mysteries. we may never know!

[@097_zarb2]

Pretty good​@@christoforoslapathiotis8064

[@sirch1984]

Thanks for helping me with my hw, you rock my dude

[@EducateYourselfNow]

I am glad I can help

[@JoseSanchez-vv1zd]

Nice explanation. Thank you.

[@iffatsarfraz5145]

I agree. Thank you so much for posting this video!

[@orangutan79]

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

[@EducateYourselfNow]

that is true, didn't think of that, thank you. i ll incorporate that in my upcoming videos

[@ZapOKill]

thats not correct. 3:00 would fail. you have to maintain a en.wikipedia.org/wiki/Disjoint-set_data_structure

[@unknownplayer0383]

dope !!!!! thanks for this video. you just did 10 times better than my professor at cal state Monterey Bay

[@andreicusnir4320]

very nice explained video! Thank you

[@EducateYourselfNow]

Thank you Andrei :)

[@xxakhilh47xx41]

Lifesaver

[@wachowski9525]

what a king, ty

[@nashb9691]

Dude i love you man

[@EducateYourselfNow]

thank you brother, i appreciate the love :)

[@JC-cu2ym]

THANKS FOR SAVING MY LIFE :D !!!!

[@amiraayedi]

Thank you for this!! (you have a nice voice though god)

[@sanjeewankulathunga]

i have exam tomorrow thanks man i got it

[@EducateYourselfNow]

i hope you did well :)

[@nooranalkhateeb8481]

the path you choose is not the shortest path

[@sanket_valani]

Nice work man :)

[@EducateYourselfNow]

thank you :)

[@zepheriah5294]

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?

[@EducateYourselfNow]

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.

[@zepheriah5294]

@@EducateYourselfNow Duh! Thank you!

[@tanss6467]

Good video, help me a lot

[@sirisunkam6011]

U r explanation too gud...pls explain bellmanford algorithm also....

[@EducateYourselfNow]

i will upload it soon

[@eyyys1342]

THANK U SO MUCH FOR THIS

[@bennybob444]

Given completely distinct edges in graph G, there is only a single MST.

[@badboybs98]

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.

[@mikewong5859]

Pretty nice, thanks.

[@EducateYourselfNow]

thank you :)

[@norueljayvillas5780]

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.

[@EducateYourselfNow]

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

[@Poojasahani12356]

Awesome sir😍😍

[@ifzahmed3973]

Thanks bro

[@monilparekh3972]

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?

[@Koo998_]

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).

[@ahmedmagdy-qg3tb]

good job

[@EducateYourselfNow]

thank you!

[@jahanzaibasgher1275]

thank you

[@mojtabavatandost3982]

thanks

[@simonhrabec9973]

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?

[@mahdiebrahimi1662]

Thank you so much! XD

[@HauNguyen-mb3si]

Thanks

[@WoosTV]

thx bro

[@prvizpirizaditweb2324]

why did not you choose both edges with weight 8?

[@cutething4910]

Thank u sir

[@Github_tech_with_ty]

Can someone explain what he mains by cycle more?

[@caparn100]

How do you programmatically test if adding the edge will form a cycle?

[@aurbakhan1019]

can anyone explain why did not we consider the other 8

[@EducateYourselfNow]

we could, it wouldn't have mattered. I think i mentioned it in the video. 3:07

[@MsKevkev1234]

if he did it would form a loop abcfgha

[@cameronfitzpatrick2489]

either way forms a mst - mst is not necessarily unique

[@samailotoke7201]

Is this the same as minimum cost arborescence?

[@halcy6422]

well you could remove the c-d, and replace it with e-f. i think it will produce better MST

[@sky76570]

In the Time Complexity part, you definitely gave a description of the runtime of the Prim's algorithm, not Kruskal's.

[@i0dan]

BIG O!

[@mohdalnokhatha521]

thanks a lot man its very helpful answer is 42 ??

[@marieselfer6621]

Isn't it 37?

[@tiberiunaznean7155]

@@marieselfer6621 i think its 37 too

[@BradleyLillian-n9h]

Hannah Lodge

[@Turkeys_VR]

It looks like C would form a cycle. Am I missing something?

[@EducateYourselfNow]

there is no loop that encloses c

[@ffs0]

Dikjstra algo??

[@azzahrahumaira6955]

if we have touched all the vertices but not all the edges yet what should i do? finish all the edges?

[@EducateYourselfNow]

yes

[@Chandler890]

so whats difference btw prims

[@EducateYourselfNow]

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.

[@dabluedevil1000]

How would choosing the edges "bh" create a cycle?

[@EducateYourselfNow]

cycle would be : b c f g h, or b h g f c

[@aldrinebarit3961]

how do you get those numbers?

[@TheBobby570]

EE241C5A ftw!!!

[@muhammadazfar97]

Can't understand about algorithm

[@almuntasirabir4511]

why did you choose both the two

[@EducateYourselfNow]

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.

[@almuntasirabir4511]

thanks

[@niklaspeura4193]

But is it still minimal is the question.

[@kma1138]

[@xiangzuo1306]

u such a copy ninja (from book introduction of algorithm)

[@Bleachiiigo]

I hate discreet mathmatcis