Kruskal's Algorithm Lecture Notes

Hello friends, welcome to Gate Smashers In this video we are going to discuss about Kruskal algorithm And in this video we are going to discuss all important points related to Kruskal algorithm Which will be very beneficial for your competitive exams, even college and university level exams So guys, like this video quickly, subscribe the channel if you haven't done it yet And please press the bell button so that you get all the latest notifications So let's start with Kruskal algorithm The first important point is, if you want to find out minimum cost spanning tree So for that we either use Kruskal algorithm or we use Prims Now what is the actual Spanning Tree? What are the properties of Spanning Tree? I had already discussed this in the last video If you haven't checked that video, then I have given its link in the description box So please check that video so that you get all the information about Spanning Tree If you already know about this case, then you can directly check this video So here in Spanning Tree, I want to find out minimum cost spanning tree So in Spanning Tree, the first property is that number of vertices should be same Means the number of vertices in our graph should be same as in Spanning Tree So see, how many vertices are there in the given graph? 1, 2, 3, 4, 5, 6, 7 So that means in the Spanning Tree that we have to make, how many vertices will be there? 7 vertices will be there, so make it in that position, 1, 2, 3, 4, 5, 6 and 7 Next point is tree, it is a spanning tree So in Spanning Tree, how many number of edges will be there? N-1 N-1 means number of vertices minus 1 So here in the graph, how many number of vertices are there? 7 So we have to make 7-1, 6 edges here And you have to select those 6 edges in this way Neither there should be any loop in it, and cost should be less than all And my graph or my spanning tree should be connected So how do we actually do this? We will discuss about the algorithm too But if you come in the exam, then you have to apply a simple technique What is the technique? That you have to calculate all these edges, whatever its weight is given You have to arrange it in your mind or on a rough page or rough sheet In a small place, arrange it in increasing order Means whatever weights you have given, whatever the weights of the edges You either keep it in your mind or write it in increasing order on a rough page Means first of all you have to pick minimum weight edge Now what is the minimum weight that I have? See this, B to E is 2 See which is the minimum? B to E, that is 2 So what are you drawing first? B to E you have drawn And write down how much weight is 2 on it Next, what is the second point here? Now pick the second edge The minimum weight one, 2 is already done, now which will be the second one? 3, so see this is the 3 one and this is the 1st one So first of all if I draw this, you can pick any one, you can pick this too Let's say I am picking this first, so you draw A and C like this Write down how much weight is 3 on it You can pick this too first, it doesn't matter Just remember that the loop should not be formed Means the cycle, actually sometimes we consider the loop as self loop So this self loop concept is not here We are working on a simple graph, the cycle should not be formed And here let's say I pick the third one, E to F So if I pick E to F, then you can write this as weight 3 Here I want to tell you an important point When we are making a spanning tree in a Kruskal algorithm So the intermediate result is not complete yet, it is half incomplete So this intermediate result can be disconnected too Disconnected means A and C are not connected with this It is disconnected but it will always be connected in the Prims algorithm So it is still disconnected here But when it will be complete then it will be connected Sometimes we ask this point in theory So remember in the Kruskal algorithm that when intermediate answer is there When your answer is not complete yet, it works in different ways Sometimes we put it here, sometimes here, sometimes here There is no connection between them, but it will be made at the end Next, here it will be 3, 2, 3 Next is what weight? Next we have 4 So see what is the 4 weight? 1 here, 1 here and 1 here You can pick any of these three first, just the cycle should not be formed Let's say I picked this first, B to C So if I pick B to C, then what is the weight? 4 I wrote 4 here Next see which is the 4th one, E to G If I pick E to G here, then we drew E to G What is the weight? 4 What is the next? Next again 4 minimum is F to G If I make F to G here, then see what is made? Cycle is made If this cycle is made here, then this spanning tree will not remain This will become a graph because there is a cycle in the graph There is no cycle in the tree So here you have to keep in mind that your cycle should not be made here Although even if it is minimum weight, even if the weight is less You still do not have to make the cycle So I remove it from here, we will not consider the 4th one Sometimes we ask this point that which edge Although its weight was less, but we did not consider it So this can also be this Because I drew this first, so I cancelled this If you take this first, then you cancel this But you have to pick only one of the two Then 4th one, which one do we have? There is no one else So after that we have 5 weight left There is 6 also, but before 6 we have 5 So see 5, A and B But see if I draw A and B here, what will become? Cycle will be made A, B, C cycle So we cannot take this, do not consider this Otherwise your question will be wrong 5, which is the next 5? So if I see this D and how much weight is 5 So see how many number of edges should be there? 6, 1, 2, 3, 4, 5, 6 So what I have is a spanning tree Minimum cost spanning tree is made Total the cost of this 3 plus 4 is 7, 7 plus 5 is 12, 14, 18, 21 So this is the, once again count 8 And this is your 12, 13, 14, 14 and 17 17 and 4, 21 So this is the right answer That is 21 is the minimum cost spanning tree If I use Kruskal In the case of Prims also this answer will be same Both the algorithms give the same answer But their method of doing is different So you can get a lot of questions like this And already in competitive exams A lot of questions come on Kruskal Because this topic is easy So many students do it easily But sometimes there are such points Such graphs give you To create confusion So you have to check very carefully here Just cycle should not be made, so this is our 21 Now let's see the last point here Its time complexity So let's say if I solve this Or we implement this algorithm through MinHeap If I do it through MinHeap So the first point is Construct the MinHeap with the E number of edges Because what we have to do is We have to sort all the edges We have to sort all the edges in increasing order So what I did is created MinHeap So as soon as we created MinHeap Obviously the minimum one will be Will come on your root In this way when MinHeap will be created Then the minimum one is 2 Means 2 will come here And how much time will it take to create MinHeap? You use the heapify method So how much time it takes? Order of E If you don't use heapify Then you can say E log E Like what is normal? L log N But here E log E Because here there is no N, there is N number of vertex So let's say the main concept that we have Which is above edges So in that case you can say E log E But if we use heapify then order of E Then take one by one edge We picked up the edge one by one Add in the spanning tree We added one by one in the spanning tree And keep in mind that the cycle should not be created And when to stop? When N-1 will come on your edges So see if we talk about best case Let's say N-1 my edges will be in the best case See how? If we see a simple graph here 1, 2, 3, 4 What is the number of edges? 4 So here when we make a spanning tree So 1, 2, 3 How much I checked out of 4? I checked out only 3 edges And what is yours? Spanning tree is made In this case N-1 edges will be used by you So for N-1 edges Means you will take out one edge here The minimum one Then what we do? Then we bring the last one here Then we rearrange it So that the second minimum comes on the root Then we pick up the second minimum Then we bring the last one up again Then what we do? We rearrange it so that the third minimum comes up Then we remove the third minimum Bring the last one up And then rearrange it so that the fourth minimum Comes on top of all This procedure In doing this procedure In doing A Log E time will be required Obviously like we take log N time In adding one element in the heapify method Or we do it in heap sort So in heap tree, min heap or max heap The time to add one element is log N But here we are talking about edges So how much time will be? Log E But how many times I will have to do this log E? In best case, I will have to do N-1 time Means the number of vertex we have Less than that Like we did here, we used 6 here So in normal case you can say N-1 log E Which can be written as order of N log E But if we talk about worst case Then you may have to travel all the edges You have to remove all the edges Let's say that all the vertices Or all the edges, sorry If I take the weight of all the edges the same So obviously you have to check every edge So in that case you can say E log E will be there Otherwise you have time complexity L log E Where N is the number of vertices So here if you do minus 1 In best case this can be in worst case You have to check all the edges Then your E log E time will be there So this is all about the Kruskal algorithm Thank You.

Hello friends, welcome to Gate Smashers  In this video we are going to discuss about Kruskal algorithm  And in this video we are going to discuss 
all important points related to Kruskal algorithm  Which will be very beneficial for your competitive 
exams, even college and university level exams  So guys, like this video quickly, subscribe 
the channel if you haven&#39;t done it yet  And please press the bell button so that 
you get all the latest notifications  So let&#39;s start with Kruskal algorithm  The first important point is, if you want to
 find out minimum cost spanning tree  So for that we either use Kruskal algorithm or we use Prims  Now what is the actual Spanning Tree? 
What are the properties of Spanning Tree?  I had already discussed this in the last video  If you haven&#39;t checked that video, then I 
have given its link in the description box  So please check that video so that you get 
all the information about Spanning Tree  If you already know about this case, 
then you can directly check this video  So here in Spanning Tree, I want to 
find out minimum cost spanning tree  So in Spanning Tree, the first property is
 that number of vertices should be same  Means the number of vertices in our graph
 should be same as in Spanning Tree  So see, how many vertices are there
 in the given graph? 1, 2, 3, 4, 5, 6, 7  So that means in the Spanning Tree that we
 have to make, how many vertices will be there?  7 vertices will be there, so make it in 
that position, 1, 2, 3, 4, 5, 6 and 7  Next point is tree, it is a spanning tree  So in Spanning Tree, how many number of edges will be there? N-1  N-1 means number of vertices minus 1  So here in the graph, how many number of vertices are there? 7  So we have to make 7-1, 6 edges here  And you have to select those 6 edges in this way  Neither there should be any loop in it, and cost should be less than all  And my graph or my spanning tree should be connected  So how do we actually do this? We will discuss about the algorithm too  But if you come in the exam, then you have to apply a simple technique  What is the technique? That you have to calculate 
all these edges, whatever its weight is given  You have to arrange it in your mind or on a rough page or rough sheet  In a small place, arrange it in increasing order  Means whatever weights you have given, 
whatever the weights of the edges  You either keep it in your mind or write 
it in increasing order on a rough page  Means first of all you have to pick minimum weight edge  Now what is the minimum weight that I have? See this, B to E is 2  See which is the minimum? B to E, that is 2  So what are you drawing first? B to E you have drawn  And write down how much weight is 2 on it  Next, what is the second point here? Now pick the second edge  The minimum weight one, 2 is already done, 
now which will be the second one?  3, so see this is the 3 one and this is the 1st one  So first of all if I draw this, you 
can pick any one, you can pick this too  Let&#39;s say I am picking this first, so you draw A and C like this  Write down how much weight is 3 on it  You can pick this too first, it doesn&#39;t matter  Just remember that the loop should not be formed  Means the cycle, actually sometimes
 we consider the loop as self loop  So this self loop concept is not here  We are working on a simple graph, 
the cycle should not be formed  And here let&#39;s say I pick the third one, E to F  So if I pick E to F, then you can write this as weight 3  Here I want to tell you an important point  When we are making a spanning tree in a Kruskal algorithm  So the intermediate result is not complete yet, it is half incomplete  So this intermediate result can be disconnected too  Disconnected means A and C are not connected with this  It is disconnected but it will always be connected in the Prims algorithm  So it is still disconnected here  But when it will be complete then it will be connected  Sometimes we ask this point in theory  So remember in the Kruskal algorithm 
that when intermediate answer is there  When your answer is not complete yet,
 it works in different ways  Sometimes we put it here, sometimes here, sometimes here  There is no connection between them, but it will be made at the end  Next, here it will be 3, 2, 3  Next is what weight? Next we have 4  So see what is the 4 weight? 1 here, 1 here and 1 here  You can pick any of these three first, just the cycle should not be formed  Let&#39;s say I picked this first, B to C  So if I pick B to C, then what is the weight? 4  I wrote 4 here  Next see which is the 4th one, E to G  If I pick E to G here, then we drew E to G  What is the weight? 4  What is the next? Next again 4 minimum is F to G  If I make F to G here, then see what is made?  Cycle is made  If this cycle is made here, then this spanning tree will not remain  This will become a graph because there is a cycle in the graph  There is no cycle in the tree  So here you have to keep in mind that
 your cycle should not be made here  Although even if it is minimum weight, even if the weight is less  You still do not have to make the cycle  So I remove it from here, we will not consider the 4th one  Sometimes we ask this point that which edge  Although its weight was less, but we did not consider it  So this can also be this  Because I drew this first, so I cancelled this  If you take this first, then you cancel this  But you have to pick only one of the two  Then 4th one, which one do we have?  There is no one else  So after that we have 5 weight left  There is 6 also, but before 6 we have 5  So see 5, A and B  But see if I draw A and B here, what will become?  Cycle will be made  A, B, C cycle  So we cannot take this, do not consider this  Otherwise your question will be wrong  5, which is the next 5?  So if I see this  D and how much weight is 5  So see how many number of edges should be there?  6, 1, 2, 3, 4, 5, 6  So what I have is a spanning tree  Minimum cost spanning tree is made  Total the cost of this  3 plus 4 is 7, 7 plus 5 is 12, 14, 18, 21  So this is the, once again count 8  And this is your 12, 13, 14, 14 and 17  17 and 4, 21  So this is the right answer  That is 21 is the minimum cost spanning tree  If I use Kruskal  In the case of Prims also this answer will be same  Both the algorithms give the same answer  But their method of doing is different  So you can get a lot of questions like this  And already in competitive exams  A lot of questions come on Kruskal  Because this topic is easy  So many students do it easily  But sometimes there are such points  Such graphs give you  To create confusion  So you have to check very carefully here  Just cycle should not be made, so this is our 21  Now let&#39;s see the last point here  Its time complexity  So let&#39;s say if I solve this  Or we implement this algorithm through MinHeap  If I do it through MinHeap  So the first point is  Construct the MinHeap with the E number of edges  Because what we have to do is  We have to sort all the edges  We have to sort all the edges in increasing order  So what I did is created MinHeap  So as soon as we created MinHeap  Obviously the minimum one will be  Will come on your root  In this way when MinHeap will be created  Then the minimum one is 2  Means 2 will come here  And how much time will it take to create MinHeap?  You use the heapify method  So how much time it takes?  Order of E  If you don&#39;t use heapify  Then you can say E log E  Like what is normal? L log N  But here E log E  Because here there is no N, there is N number of vertex  So let&#39;s say the main concept that we have  Which is above edges  So in that case you can say E log E  But if we use heapify then order of E  Then take one by one edge  We picked up the edge one by one  Add in the spanning tree  We added one by one in the spanning tree  And keep in mind that the cycle should not be created  And when to stop?  When N-1 will come on your edges  So see if we talk about best case  Let&#39;s say N-1 my edges will be in the best case  See how?  If we see a simple graph here  1, 2, 3, 4  What is the number of edges? 4  So here when we make a spanning tree  So 1, 2, 3  How much I checked out of 4?  I checked out only 3 edges  And what is yours? Spanning tree is made  In this case N-1 edges will be used by you  So for N-1 edges  Means you will take out one edge here  The minimum one  Then what we do?  Then we bring the last one here  Then we rearrange it  So that the second minimum comes on the root  Then we pick up the second minimum  Then we bring the last one up again  Then what we do?  We rearrange it so that the third minimum comes up  Then we remove the third minimum  Bring the last one up  And then rearrange it so that the fourth minimum  Comes on top of all  This procedure  In doing this procedure  In doing A  Log E time will be required  Obviously like we take log N time  In adding one element in the heapify method  Or we do it in heap sort  So in heap tree, min heap or max heap  The time to add one element is log N  But here we are talking about edges  So how much time will be? Log E  But how many times I will have to do this log E?  In best case, I will have to do N-1 time  Means the number of vertex we have  Less than that  Like we did here, we used 6 here  So in normal case you can say  N-1 log E  Which can be written as order of N log E  But if we talk about worst case  Then you may have to travel all the edges  You have to remove all the edges  Let&#39;s say that all the vertices  Or all the edges, sorry  If I take the weight of all the edges the same  So obviously you have to check every edge  So in that case you can say  E log E will be there  Otherwise you have time complexity L log E  Where N is the number of vertices  So here if you do minus 1  In best case this can be in worst case  You have to check all the edges  Then your E log E time will be there  So this is all about the Kruskal algorithm Thank You.

Transcript for:Kruskal's Algorithm Lecture Notes

Transcript for:
Kruskal's Algorithm Lecture Notes