# Kruskal’s Algorithm for Minimum Spanning Tree | GeeksforGeeks

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

## 55 thoughts to “Kruskal’s Algorithm for Minimum Spanning Tree | GeeksforGeeks”

1. Hardik Sanghavi says:

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

2. Vijay Bhargav G says:

3. Kunal Jain says:

4. Nands says:

Have you done a video on Prims?

5. Sam Slim says:

How to find the second spanning tree ? thanx

6. Anchal Dua says:

7. Arnab Ray says:

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

8. LET'S DO IT says:

find and union operations take O(E) time??????
Verify it.

9. Amitya Narayan says:

very nicely explained thanks

10. Poonam Agrawal says:

Videos are not in sequence

11. Poonam Agrawal says:

very nicely explained thanks

12. Bhumika Gupta says:

Thanks alot man ❤

13. thetruereality says:

the pseudocode was not clear

14. Gabrielle Marcum says:

thank you so much this helped a lot

audio 🙁

16. Deepak Sahani says:

nice….

17. Ravi Agarwal says:

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

18. Álvaro Carvalho says:

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

19. Siddhesh Deshpande says:

my right ear enjoyed this

20. tapanjeet roy says:

thanks a lot sir…

21. Anamika Sudheesh says:

Well explained

22. Nishant Aochar says:

Great

23. Zeel Patel says:

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

24. Siri Sunkam says:

Too speed…..😥

25. A R DANISH says:

good

26. edvinas132 says:

Line 2 and 3 create vee trees?

27. Rohit HT says:

Pseudocode not understanded

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

30. Nanz kumar says:

Great explanation sir!!!

31. Uttarakhand trekkers says:

Thanks sir!

32. M_ MIX says:

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

33. Md Sahil says:

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

34. Ahamed Rafy says:

can you give me the krushkal algorithom in c program

35. Prateek Krishna says:

Thanks

36. Raghav Gupta says:

Good

37. ritesh geddam says:

Very well explained!!!

38. Sw yx says:

short and sweet. well worth the 5 minutes

39. Linux Tubers says:

Thanks

40. 钟懿 says:

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

41. SINGAVARAPU RAMYA LAKSHMI says:

great explanation sir….thankyou

42. Dr F says:

Thanks good and useful example

43. Sujay S Shenoy says:

The idea of sorting the weights before using algorithm was awesome

44. Snazzle Live KBC says:

balance the audio please … so irritating

45. Siddarth Karki says:

I thought my left ear phone stopped working xD
Amazing video though , Thanks a lot! 🙂

46. Shaurya OP says:

Bestest

47. abhinav gupta says:

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

48. miss arya says:

Shortly and clearly explained

49. vicky cool says:

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

50. CodeVary says:

51. Pintu Saini says:

Go little slow 😴

52. Selay Tekgül says:

I like G4G

53. Parth Kandwal says:

Thanks a lot

54. 王佩玲 says:

Great
Explanation!

55. I Carry the Night says:

non-decreasing order? sounds confusing to me