Kruskal’s Algorithm
In this blog we’ll talk about Kruskal’s algorithm, its’ working, where its used and its applications.
Kruskal’s algorithm is used to generate a Minimum Spanning tree for a given graph. A minimum spanning tree(MST) is a subset of a graph with the same number of vertices(V) as the graph itself and edges(E) equal to number of vertices-1.
E=V-1
Kruskal’s algorithm sorts all the edges in ascending order of edge weights and adds nodes to the tree only if the selected edge does not form a cycle. It also chooses the edge with the lowest cost first and the edge with the highest cost last. As a result, the Kruskal algorithm makes a locally optimum decision in the hopes of finding the global optimal answer. For this reason it is termed as a Greedy Algorithm.
The steps involved in generating an MST using Kruskal’s Algorithm are:
1. Sort all edges in an ascending order of their edge weights.
2. Pick the edge with lowest edge weight and check if it form a cycle or loop in the spanning tree.
3. If the edge doesn’t form any cycle or loop, then include the edge in the MST, otherwise, discard it.
4. Repeat steps 2 and 3 until the MST has V-1 edges.
*Note: If the given graph has any loops or parallel edges, you must remove all loops and parallel edges from the given graph.
In case of parallel edges, the edge with the least weightage is retained and the others are removed.
Let us consider an example to understand Kruskal’s algorithm:
=>We remove all loops and parallel edges from the graph.
=>We remove the parallel edge which has more weight.
=>We arrange the edges in their increasing order of weight.
=> We start adding edges to the graph starting from the least weighted edge while keeping the spanning properties intact.
The least weighted edge is 2. Hence the edges (B,D) and (T,D) are chosen and it is verified that they do not violate spanning tree properties.
Next least weighted edge is 3 and the edges (C,D) and (A,C) are added with spanning tree properties remaining intact.
The next least weighted edge is 4 associated with edge (C,B) but adding this edge would introduce a loop (C, B, D) in the graph. hence it is discarded.
The next weighted edges are 5 and 6 in the table and introducing either of these edges would violate the spanning tree properties. hence both these edges are discarded.
Now the only node left is node S and it can be associated with edge (S, A) or (S, C) with weightage of 7 and 8 respectively. We select the edge (S, A) with the lower weightage i.e. 7. And now we have the MST.
The Time Complexity for Kruskal’s algorithm:
T(n)= O(1) + O(V) + O(E log E) + O(V log V) = O(E log E) + O(V LOG V)
|E| ≤ |V|²
log |E| < log |V|²
log |E|< 2 log |V|
Since |V| > |E| +1
T(n)= O(E log V)
Conclusion
We examined Kruskal’s Algorithm and utilized it to construct the minimum spanning tree for a given graph topology. We also derived the Time Complexity for Kruskal’s Algorithm and it was found out to be O(E log V).