Hello friends my name is Tushar and

today we’re going to talk about how to find minimum spanning tree using

Kruskal’s Algorithm. So what is a spanning tree? A spanning

tree of an undirected graph is a sub graph such that all the vertices are

connected to each other and then there is n-1 edges in this subgraph where n

is the total number of vertices. So basically the subgraph represents a

tree. What is the minimum spanning tree of a

weighted undirected graph? A minimum spanning tree is a tree,

is a spanning tree such that the sum of the weight of the edges is minimum. So if you look at this example here the

minimum spanning tree for this graph will consist of three edges (A,B),(B,C) and

(D,C).So we have 4 vertices, we have 3 edges and all the 4 vertices are

connected to each other to form a tree. So for this video I assume that you know

what disjoint sets is because it’s a pre-requisite to understand this

algorithm. I have another video discussing

disjoint sets using path compression and if you have not already watched that video

please watch that video before watching this video. So in the next section let’s try to find

the minimum spanning tree for this example here. The idea of this algorithm

is very simple. First thing we do is we sort the edges

in non decreasing order,then using this makeSet operation of disjoint sets we

create as many disjoint sets as the number, total number of vertices. Then we pick

one edge at a time in the non decreasing order and check both the ends

of this edge and see if they’re in the same disjoint sets or different. If they are in the

same disjoint set we ignore this edge if

they are in different disjoint sets we merge those disjoints sets into 1 and put this

edge into the final result. So let’s try with this example here. So

i’ve already created 6 different disjoint sets and I have already sorted

edges in non decreasing order so first let’s pick this edge (A,D). So ‘A’ and ‘D’ are in 2 different

disjoint sets. So we’ll pick (A,D) into final result and using this union operation of

disjoint set we’ll merge ‘A’ and ‘D’.So this will become ‘A’ and ‘D’ in 1 set. Then we are going to pick

the next edge (B,C). So 1st we’re going to check,’B’

and ‘C’ again are in 2 different disjoint sets so (B,C) is also going to be in the

final result and we’re gonna merge ‘B’ and ‘C’ using this union operation of disjoint sets. Then we’re going to pick edge (C,D).

So let’s say this disjoint is represented by ‘A’ and this disjoint set

is represented by ‘B’, so we’ll do findSet and find ‘C’ and ‘C’ belongs to set ‘B’ and we

do a findSet and find ‘D’ and ‘D’ belongs to set ‘A’. So basically they are in two

different disjoint sets so we’ll again pick (C,D) for the final result and

do the union of these two sets.So we’ll have one set here (A,B,C,D) and let’s say this set is

represented by ‘A’ so then we are going to pick (E,F),so ‘E’ and ‘F’ are in 2 different disjoint sets.So

(E,F) is also in the final result and we’re gonna do union of ‘E’ and ‘F’. Then we’re gonna pick the next edge (B,D).So

‘B’ is represented by ‘A’ and ‘E’ is represented by ‘A’ which tells us that

‘B’ and ‘D’ are in the same disjoint sets right now,so we’ll just ignore this edge.

Then we’ll pick the next edge (A,B).’A’ is represented by ‘A’ and ‘B’ is also

represented by ‘A’ which tells us that ‘A’ and ‘B’ are in the same

disjoint set,so again we’ll ignore this edge here (A,B). Then we’ll pick the next edge (C,F). So ‘C’ is,’C’ is in the set ‘A’ and ‘F’ is the set ‘E’ and so they are in two

different sets So we’ll again pick this edge (C,F) and merge

these 2 disjoint sets. And then we’ll pick (C,E) and ‘C’ is represented by and ‘C’ is

represented by ‘A’ and ‘E’ is represented by ‘A’ which tells us that ‘C’ and ‘E’ are in the

same set so we’ll again ignore this edge. And lastly (D,E), ‘D’ is represented

by ‘A’ and ‘E’ is represented by ‘A’,basically telling us that they are also in the same they’re also in the same disjoint set,

so we’ll again ignore ‘D’.So these are the edges which form the

minimum spanning tree for this graph here. (A,D),(B,C),(C,D),(E,F) and (C,F) here.So this 5

edges form together minimum spanning tree. So what is a space complexity? Space

complexity is,in the worst case whatever disjoint sets takes and whatever this result,whatever we’re storing the result

so it will be O(V+E). What is the time complexity for this algorithm? So it will take,so if we have ‘E’ edges it will take O(ElogE) time to

sort these edges in non decreasing order and then if you have watched my video on

disjoint set so you would know that if,if there are

‘n’ operations on disjoint set it takes O(n) time. So rest of this operation would in worse

case take O(E) time,so O(ElogE+E). So in the next section let’s look at the code for this algorithm.

Code like algorithm is very simple. So the name of the function is get

minimum spanning tree and it passes us a graph.First thing we do is we get all

the edges of this graph and then we sort the edges in non decreasing order

and then we initialize a class of dis- -joint sets,set and what we do is we

create as many disjoint sets as the total number of vertices using this

makeSet operation of disjoint set. And then we are going to do is iterate

through each of the edges in non decreasing order and for every edge,

get the 2 vertices of this edge and see if they are in same disjoint set or

different disjoint set.So we get the root, we get the name of the set for all,

for these 2 vertices of the edge using findSet operation and

check if they are in the same set.If they’re in the same set it means we’re

going to ignore this edge and if they’re in the different set then we’re going to

add this edge into the final result and also do the union of these 2 sets into

1 and then we move on to the next edge and we keep doing this until we have

edges to iterate through. And then finally return all the edges in the result edge.So

as I said again the runtime complexity is O(ElogE) to sort this,the

edges and then O(E) to do these operations and the space complexity is

O(E+V). Thanks again for watching this video.

Please like this video,share this video comment on this video,check out my

facebook page at facebook.com/ tusharroy25 and check out my github

link github.com/mission-peace/ interview/wiki. Thanks again for watching this video.

your videos are really helpfull

For your next video, can you explain dijkstras algorithm?

You are great..! helped me alot..!

At 5:45 , you ticked BD instead of CD

Suggestion:- I found it better in earlier few of your vids where you wrote pseudo code on board(ie explain each line as you go along) instead of this method

Thanx for the vid

You made all the graph algorithms look so easy with your tutorials. I enjoy your videos. Keep them coming !!!!

sir you are really great in explaining these videos

can you please put up a video on fractional knapsack and task scheduling program

you sir helped me alot in my first sessionals in ada.

Is this a union by size or union by height?

Can't we stop stop the algorithm once we get all the nodes in one set? Why do we need to check for CE and DE?

Thanks very much man

Wow, Really it saved 4 hrs of reading a DS and Algo text book. Thank u very much.

And a small request is please speak little slow(speed). Thanks again for great video..

An excellent video. I do appreciate.

Can you please provide a lecture on Random Walk for a Weighted Graph ?

No offense, you speak very fast!

good lecture on graphs and trees

good lecture on graphs and trees

hi,

can you give me c code in kruskal?

Great video. Is there a video for Arborescence?

Please mention the pseudo codes in your videos aswell. Thanks

Really very helpful. Good job sir….Thanx a lot!!

Amazing video sir. Thank You.

thats all? o.O that easy?

You get confused in this video :p

شرح رائع شكرًا

sir speed is very fast

Thank you, Tushar! This video was helpful for my understanding

thanks a lot , it was helpful video

Thank you so much! Your explanation is very clear ^^

Can you please explain what is edgeComparator here?

Best explanation i found on the web. Thank you a lot, keep going on !

Please have a tutorial on Breadth first search and depth first search,overall your tutorials are great 🙂

one mistake..BD is not finally result…pl rechange BD into CD

It would be helpful if you could add the link to the video for disjoint sets here. Other than that good job..love ur videos.

thank you so much you cleared my doubt

How do I get a path between 2 nodes (along this MST) assuming I have the result set of edges?

In your Dijkstra video, it was clear.

u marked bd instead of cd in the final answer……. very helpful video thanks a lot bro……..

Very Nice Tuts and awesome for learning each topic in depth. Can we stop the edges iteration when disjoint set size equals to Vertices count in Graph?

please provide c++ implementation ….

It's CD and not BD at 5:44

East or west tushar sir is the best

cant see the board bcz of subtitles

sir bd path is not present in answer … it should be cd

Actually in this video u ignored the edge BD but in last u ticked why is this so?

Thank you brother we passed our exams because of your videos without your clips we are getting big trouble brother….thank you very much..

great class Sir..!….Thank u so much.

thank you teacher!

Very well explained thanks a lot!!

i din understand how to calculate space complexity

good

You're a legend.

Good one.

that was amazing

chuss video

Thanx a ton, would be much better if you explained Pseudo code instead of actual code! other than that great work

Sir, why is it phut and not put..please it irritates..

At 5:45 it is cd not bd

Good work Tushar. Thank you.

I know in some videos you use colored markers, I think it makes it easier to follow

Hi, my friend, you don't need to erase the nodes and rewrite them again and again. That makes me feel uncomfortable!

good video, but please talk more quietly

Clearly Explained, Thanks.

If the edges are already sorted then the time complexity comes down to O(n) right?

bro how are you representing the graph.. do u have a package called Graph so that u can use Graph<>,Edge<> etc… ?

i cant find them .. i mean i wrote the whole code nd im unable to figure out what should be the arguments in the classes GRAPH and EDGE which matches the arguments in "findSet and Union" in your "Disjoint set"

Whoa!!! What was the beginning like??? You seemed more like a robot with zero expression…

Very good explanation

Why do we sort the edges? how does that help in the execution?

nice explanation sir

Nice and crisp explanation.

Well explaned 🙂

Great Video

you are a god

Complete code: https://goo.gl/8TMkTt

Bhai ye tw jyada he angrez banra😂

bekaaarrr …….vdo

what about algorithm for Minimum Spanning tree from a undirected and unweighted graph??

it was really nice thanks

chuss

Answer for the above graph if done manually 9 units. Hit like or comment if anybody donesir can you please watch my tutorial . .this is only a project of my course ..the more views the highest grade i can get . .so please sir for the sake of my studies .

তীরে এসে তরী ডুবিয়ে দিলো।😂😂😂😂😂উত্তর 4+2+1+1+1=9 হবে।।

At 5:44 the edge should be C-D with cost 1 instead of B-C with cost 3.

again, you are the best. i have a basic question. i don't understand what problem this algo is trying to solve. it is not minimum optimal path algo.

we can stop processing edges once the result set has (|V| -1 ) edges. this will save some time.

In your github repo, you have mentioned the time complexity as 0(ElogE) in place of O(ElogE + E)

bhai.. thanks a lot!

I always click your video first when I search an algorithm in YouTube. Thanks!

I'm not good in algorithm, I'm not so good in english but you make it so simple that also me understood xD

0 to 0.20 like Tushar was an adrenaline rush !!

explain the time complexities instead of just stating it

for(true){

"thank you" ;

}

Thank you so much , your tutorial are so easy

god of ds

MC

the best!

Satisified 😊

Gautam gambhir's double

y r we using disjoint set is because we dont want cycles

plzz give code of beginners level, dont use inbuilt methods