Kruskal’s algorithm for computing minimum

spanning tree of a graph. Now, let’s start off with some basic definitions.

What is a spanning tree? A spanning tree is a subgraph that has the same vertex set as

the original graph and is also a tree which means that it must be connected and must not

contain any cycles. A graph may have large number of spanning trees but not all of them

are minimum. A minimum spanning tree is the one in which the sum of weight of edges is

minimum Now, let’s look at the steps for finding

the minimum spanning tree using Kruskal’s algorithm. The steps are fairly simple. The

first one says sort all the edges in non-decreasing order of their weight. Now, this is a greedy

algorithm. So, what it does is that it picks the smallest weighted edge not in the spanning

tree. Checks if adding this edge to our spanning tree obtained so far forms a cycle or not.

If not, then this edge will be a part of our minimum spanning tree. If it forms a cycle,

we discard it. We need to keep repeating this step for all edges in G until there are exactly

V-1 edges in our minimum spanning tree where V is the number of vertices in G. Now, let’s try and understand these steps

with an example. Consider the given graph which has 9 vertices, v0 to v8. The numbers

on the edges represent the weight of that edge. We need to obtain a minimum spanning

tree of the given graph. The 1st step says sort all edges in non-decreasing order by

their weights. Let’s do that. You can see that all the edges

are written in the sorted order by their weights. v7v6 being the smallest weighted edge with

weight 1 and v3v5 being the maximum weighted edge with weight 14. Now, let’s move on to

step 2. Pick the smallest edge v7v6. Being, the 1st

edge, it obviously does not form any cycle. So, this edge will definitely be a part of

the minimum spanning tree. The edges represented by the yellow lines are the ones that are

part of our MST. Let’s pick the next edge v8v2. Again, it doesn’t

form any cycle, so it will be added to the MST. Next is v6v5. Again, no cycle being formed.

Add it to the MST. Now Pick v0v1, check for cycles. No cycle

formed, add this edge to the MST too! Next is v2v5, again adding this edge to MST

doesn’t form a cycle. This edge will also be a part of the MST Now, let’s look at v8v6. If we add this edge

to MST, it forms this cycle, as you can see here. So, this edge won’t be a part of the

MST. Adding v2v3 to the MST doesn’t lead to the

formation of any cycles. So, v2v3 will also be an edge in the MST. Now, v7v8 can’t be a part of the minimum spanning

tree because adding this edge would form this big cycle, this one. Adding v0,v7 to MST doesn’t form any cycle.

So, it will be added to the minimum spanning tree too. Also, note that we’re keeping a

track of the no. of edges in MST. because according to the 3rd step, we need to stop

as soon as we have V-1 edges, which is 8 in this case. Let’s try and add v1v2, note that a cycle

is being formed, so v1v2 won’t be in the MST. Next is v3v4. Adding v3v4 doesn’t form any

cycle. So, add this edge to the MST. Note that we have now 8 edges in our minimum spanning

tree. So, we have reached the terminating condition. Thus, we have successfully obtained the minimum

spanning tree of the given graph. We can also calculate the weight of this MST by adding

the weight of individual edges in this tree. We see that they add up to 37. Now, let’s have a look at the pseudocode for

this algorithm. Line 1 initializes A to an empty set.

Lines 2 and 3 create V trees, each containing one vertex.

Line 4 simply sorts all edges in the original graph by no decreasing order of their weights.

In lines 5-8, we one by one pick edges in the order of their weight, lowest to highest.

The loop checks for each edge u,v , whether the end points u and v belong to the same

tree. If they do, adding them to the MST would form a cycle. So, it’ll be discarded. But

if not, line 7 adds edge uv to the MST. Line 8 merges the 2 trees using u and v.

Finally, return the set A containing all the edges belonging to the minimum spanning tree. Now, let’s analyse the complexity of Kruskal’s

algorithm for minimum spanning trees. Initializing A to an empty set takes constant

time. The make set operation in lines 2 to 3 grows

very slowly. Sorting E edges takes O(ElogE) time

Lines 5 to 8 perform the find set and union operation for each edge in G. Thus, taking

a time of O(ElogV) So, Overall Complexity of Kruskal’s algorithm

is O (E LogE + E LogV). But value of E can be atmost O(V2), so O(LogV) and O(LogE) are

same in this case. Therefore, overall time complexity is O(ElogE) or O(ElogV). Thank you for watching the video. Please leave

us your comments.

Sir, could you put some light on the space complexity as well? Thanks in advance.

Please explain using code. That would be much helpful

Please run through the code.

Have you done a video on Prims?

How to find the second spanning tree ? thanx

very helpful video….:)

is there any video of Dijkstra? Prim's and Kruskal's are still easy to understand but Dijkstra troubles me a lot 🙁

find and union operations take O(E) time??????

Verify it.

very nicely explained thanks

Videos are not in sequence

very nicely explained thanks

Thanks alot man ❤

the pseudocode was not clear

thank you so much this helped a lot

audio 🙁

nice….

Clearly explained the process of minimum edges selection and algorithm complexity is bit helpful..

Thanks you

My left ear still doesn't know the Kruskal's Algorithm, but my right ear got it. Thanks!

my right ear enjoyed this

thanks a lot sir…

Well explained

Great

please include this video in graph data structure playlist and also prim's algorithm

Too speed…..😥

good

Line 2 and 3 create vee trees?

Pseudocode not understanded

Madarchod thora dhira bola kar

Bro u missed one point.Maximum edges in minimum spanning tree is v-1.where v no. of vertices.

Great explanation sir!!!

Thanks sir!

bohat bhala kam kar rahe ho tum sab……jannat me jaooge

very clear tutorial, thanks , proved to be a lot of help (pseudo code could have been clearer)

can you give me the krushkal algorithom in c program

Thanks

Good

Very well explained!!!

short and sweet. well worth the 5 minutes

Thanks

the voice sounds really like the doctor Zola from Hydra in Captain America…..

great explanation sir….thankyou

Thanks good and useful example

The idea of sorting the weights before using algorithm was awesome

balance the audio please … so irritating

I thought my left ear phone stopped working xD

Amazing video though , Thanks a lot! 🙂

Bestest

its funny. i feel like i m listening to cormen(audio version)

Shortly and clearly explained

thank god i came to the comments section or else i was about to replace my earphones with a new one, thinking that it stopped working partially

Really Helpful, Thanks!

Go little slow 😴

I like G4G

Thanks a lot

Great

Explanation!

non-decreasing order? sounds confusing to me