Kruskal's Algorithm
8 min read
If you're a Computer Science Student or willing to be a; you'll definitely
come through this Kruskal and many other Algorithm. In a Simple Language,
Kruskal's Algorithm is a Minimum Spanning Tree Algorithm that gets a graph
as input and retrieve the subset of the edges of that respective graph
and which ahead forms a tree that include every vertex which has minimum sum
of weightage among all of the trees that can be formed through a graph.
This Kruskal's Algorithm works as a detector and finds a minimum spanning
forest of an undirected edge-weightage graph.
Consider, If a Graph is connected, it finds a minimum spanning tree.
In this article, we'll also discuss the following elements like complexity,
working, few examples and proper implementation of
Kruskal's Algorithm.
But, I would like to make pause here and recommend you to
first understand the basic terms such as Spanning Tree and Min. Spanning
Tree.
- Spanning Tree - Spanning Tree is the subgraph of a connected graph (i.e. undirected).
- Minimum Spanning Tree - It can be defined as the spanning tree in which the sum of all weightage of all edge would or is Minimum.
Now, Let's Start with the Main Topic:
What is Kruskal's Algorithm?
Answer - Kruskal's Algorithm is used to retrieve the minimum
spanning tree for a a connected weighted graph.
The Main Aim of this Algorithm is to find the Subset of all edges by using
the method of which we can traverse each vertex of the respective
graph.
This Kruskal Algorithm follows the Greedy Method by which it can find the
optimum solution at each level.
Applications of Kruskal's Algorithm -
- It can be used to lay down LAN (Local Area Network) Connections.
- It can be used to layout electrical wiring among larger distanced cities.
Working of Kruskal's Algorithm -
In Kruskal's Algorithm, we start our execution from edges with the lowest
weight and keep increasing or adding the edges until the final goal is
achieved.
Complexity of Kruskal's Algorithm -
Here there's a Time Complexity in Kruskal's Algorithm, Let's
See.
Time Complexity - of Kruskal's Algorithm is
O(E logE) or O(V logV), where V is only the
Number of Vertices, and E is Number of Edges.
Here are the Following Steps for Solving Kruskal's Algorithm:
- Start Sorting all the Edges from Low Weightage to High-One.
- Now, take the Edge with Lowest Volume or Weightage and keep adding it to the spanning tree. If the Edge, starts creating a loop or cycle then reject the edge.
- Continue to add the the edges until and unless you reach all the vertices and until the minimum spanning tree is built or created.
Let's take an Example to Solve - It will become easier to understand
using an example. Let's see an example. Go!
Consider, a Weightage Graph is:
All the Readings of the diagram are given below.
Now, Let's sort the edges provided above in the ascending order according
to their weights.
Now, Let's Start the Building Process or Constructing a Minimum Spanning
Tree.
Tip - While Formation, Do Reject or Discard the Edges which are creating Loop/Cycle.
Step-by-Step Procedure:
Step 1 - First, add the Edge AB with weight 1 to the
MST (Minimum Spanning Tree).
Step 2 - Now, Add the Edge DE with weight 2 to the
MST (Minimum Spanning Tree) as it's not creating the Cycle.
Note: MST stands for 'Minimum Spanning Tree'
Step 3 - Add the Edge BC with weight 3 to the MST,
as it's not forming cycle or a loop.
Step 4 - Now, Pick the Edge CD with Weight 4 to the
MST, as it's not forming the loop/cycle.
Step 5 - Then, go for the edge AE with weight 5.
I think, In my Opinion, this will create a loop/cycle, then it's better to discard it.
Step 6 - Pick the Edge AC with weight 7. This will
also create a cycle or loop so we need to discard it.
Step 7 - Pick the Edge AD with weight 10. Same, this
will also create a loop in MST, so Discard it.
So, now there's no Edge Remained, So the Step 4 was the Final
Formation of MST because after there no MST has been developed. due to
formation of loop/cycle.
Note: Only Calculate the Edges which are pre-resulted as "Not Creating Loop/Cycle" while formation. Because this kind of Edges are only Eligible for Final Calculation. Edges which create Loop/Cycle are not Eligible and Hence Trashed.
See, In the Final Calculation - We have taken Step 1, Step 2, Step 3 and Step 4; because this steps are not creating any Loop or Cycle. So, the Edges from this Steps are Granted for Calculation. And Step 5, Step 6 and Step 7 are creating a Loop/Cycle so they will not be considered in Final Calculations.
So, the Final MST (Minimum Spanning Tree) resulted from the given
weighted graph is solved by using Kruskal's Algorithm.
The Final Layout of MST is given below -
Moving towards the calculation,
the cost of the
MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10
So, the Algorithm Needs to Stop Here as the Result is Out.
Data Structure Learning is a Necessity - Harshal Suryawanshi