Kruskal's Algorithm
Overview
Kruskal's algorithm is a greedy algorithm in graph theory that is used to find the Minimum spanning tree (A subgraph of a graph $G(V,E)$ which is a tree and includes all the vertices of the given graph such that the sum of the weight of the edges is minimum) of a given connected, weighted, undirected graph.
In case, the graph is not connected, on applying Kruskal's algorithm we can find the MST of each connected component.
Takeaways
Complexities of the Kruskal's Algorithm
 Time Complexity :$O(E*log(E))$
 Space Complexity:$O(E)$
Introduction to Kruskal’s Algorithm
Suppose that there are some villages in a town, you being the Mayor of the town want to visit all the villages but you have very little time for it.
So you will be interested in visiting the villages in such a way that the total distance covered by you during the visit is minimum possible. Isn't it.?
If you try to formulate the above problem in terms of graph theory, by considering villages as the vertices, roads connecting them as the edges, and the distance of each road as the weight of the corresponding edge.
Kurskal's algorithm will help you in this case because it is used to find the minimum spanning tree (MST) of any given connected, weighted, undirected graph. Before discussing any further details of Kruskal's algorithm let's see what is meant by a Minimum spanning tree of a graph.
A spanning tree is a subgraph of a connected, undirected graph such that it is a tree and it includes all the vertices. So a minimum spanning tree would correspond to a spanning tree with the minimum weight. Where the weight of a spanning tree is the sum of the weight of the edges present in it.
For Example:
The belowgiven image shows a graph $G$ with 6 vertices and 9 edges
This graph can have multiple spanning tree some of which are shown below with their respective weights.
But they can not be considered as minimum spanning trees as there exists at least one spanning tree with an even smaller sum of edge weights. The MST of the graph is 
The MST of the given graph has a weight of 17, which means that we can't form any other spanning tree of graph $G$ whose weight is less than 17.
Kruskal's Algorithm Implementation
The main idea of Kruskal's algorithm to find the MST of a graph $G$ with $V$ vertices and $E$ edges is
 to sort all the edges in ascending order according to their weights.
 Then select the first $V1$ edges such that they do not form any cycle within them.
One thing that can be observed here is, that for any graph with $V$ vertices, we are interested in including only $V1$ edges as part of the MST. It is because we need only that many edges to include all the vertices.
Let us understand how Kruskal's Algorithm works by the following algorithm and example
Algorithm of Kruskal's
For any graph, $G=(V,E)$, finding an MST using Kruskal's algorithm involves the following steps 
 Sort all the edges of the graph in ascending order of their weights.
 Check the edge with minimum weight, if including it in the answer forms a cycle discard it, otherwise include it in the answer.
 Repeat the above step until we have chosen $V1$ edges.
Example of Kruskal's Algorithm
Let's say we want to find the MST of the underlying connected, weighted, undirected graph with $6$ vertices and $9$ edges
Now as per the algorithm discussed above, to find the MST of this graph 
 We will write all the edges sorted in ascending order according to their respective weights
 Then we will select the first $V1=5$ edges which do not form cycles.

Step 1  Sort the edges in ascending order. Here is the list after sorting.
No. $u$ $v$ Weight 1 4 5 2 2 4 6 2 3 3 4 3 4 2 3 3 5 3 5 4 6 5 6 5 7 2 5 6 8 1 2 7 9 1 3 8 
Step 2  Choose 5 edges from starting which do not form a cycle.

Checking edge $4\Longleftrightarrow 5$  This is the first edge so it can't form any cycle hence including this in result 

Checking for edge $3\Longleftrightarrow 4$  Including this edge in the result does not form any cycle.

Checking for edge $2\Longleftrightarrow 3$  Again including this edge in the result does not form any cycle.

Checking for edge $3\Longleftrightarrow 5$  Including this edge in the result forms a cycle $3 \rightarrow 4 \rightarrow 5 \rightarrow 3$, hence not including this in the result.

Checking for edge $5\Longleftrightarrow 6$  Including this edge in the result forms a cycle $4 \rightarrow 5 \rightarrow 6 \rightarrow 4$, hence not including this in the result.

Checking for edge $2\Longleftrightarrow 5$  Including this edge in the result forms a cycle $2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2$, hence not including this in the result.

Checking for edge $1\Longleftrightarrow 2$  Including this edge in the result does not form any cycle. By including this, we have included 5 edges so now the result will correspond to the minimum spanning tree.

After including all $5$ edges, the MST will look like this 
So the weight of MST can be calculated as $7+3+3+2+2=17$.
Pseudocode of Kruskals Algorithm
Code Example of C/C++, Python
To efficiently check whether including an edge forms a cycle or not, we will use an already discussed concept $i.e.$ DisjointSets. We will proceed as per the pseudocode and algorithm discussed above, $i.e.$ firstly sorting the list of edges and then including $V1$ edges that do not form cycles. Find function of DSU will be used before including any edge in the MST to check if both the endpoints (nodes) of the edge belong to the same set or not. If they do not belong to the same set, we will include that edge in the MST as including the edge is not forming any cycle. Now we will use the union function of DSU to merge the two disjoint sets. Before going into the code, let's see its blueprint 
Variables 
 $V$  A global variable that will denote the number of vertices present in the graph.
 $E$  Again a global variable denoting the count of edges present in the graph.
 $edges$  A list of edges that will be sorted and then used in the Kruskal algorithm.
Method 
 $MST\_Kruskal$  A function that is responsible to find the MST of a given graph implemented as discussed in the algorithm and pseudocode.
FutureProof Your Coding Skills! Join Our Best DSA Course for InDepth Algorithmic Understanding. Enroll Now!
C/C++ Implementation of Kruskal's Algorithm
Java Implementation of Kruskal's Algorithm
Complexity Analysis
 Time Complexity 
 Sorting of $E$ edges costs us $O(E*log(E))$ time.
 For each edge, we are using the UnionFind algorithm which costs us $O(E*\alpha(V))$ time.
 As discussed in DSU, for practical values of $V$, $i.e.$ $V\leq 10^{80}$ we can write $O(E*\alpha(V))$ as $O(E)$ because $O(\alpha(V))$ $\simeq$ $O(1)$.
 Space Complexity  We are using a List/Vector to store the $E$ edges of the given graph so the space complexity is $O(E)$.
Applications of Kruskal's Algorithm
MST's which can be found using the Kruskal algorithm has the following applications 
 Innetwork designing, finding MST tells you the minimum amount of wire needed to connect all the nodes (servers).
 Approximation of NPHard problems, like we can use MST to solve the traveling salesman problem.
 It is used in autoconfig protocol for ethernet bridging, which helps to avoid cycles in a network.
 All other graph theory problems where we need to visit all the vertices with minimum cost.
Become a master of data structures with our Data Structures in C++ Free Course. Start your journey today!
Conclusion
 In this article, we have learned what is meant by the spanning trees of a graph and what is the minimum spanning tree with the help of examples.
 We have seen Kruskal's algorithm which is a greedy algorithm to find an MST of any given weighted, undirected graph.
 At last, we have analyzed its time and complexity and space complexity and seen some of its major applications.