Kruskal’s Algorithm
Hello and welcome to my blog! Today I’d like to talk about a component of the greedy approach, commonly known as Kruskal’s algorithm, that calculates the least cost of a graph’s Minimum Spanning tree, or MST. So, what is the cost, what is the lowest spanning tree, we’ve heard of graphs but not this kind? As a result, replies to all of your questions will be sent shortly.
For a better example, suppose you need to travel somewhere quickly and don’t know which route to take, so you whip out your phone and search for google maps or apple maps, depending on which device you’re using, enter the destination you want to visit, and voila! You took the shortest and least congested route to your destination.
So, maps coupled the Kruskal’s principle with a little of Prisms and the Dijkstra Algorithm to produce the desired result.
What exactly is GREEDY, and how does Kruskal’s Algorithm fit into the Greedy Algorithm subset?
A greedy algorithm is defined as an algorithm that chooses the best answer for a given period without considering the repercussions. This indicates that the algorithm will select the best-required solution for the current stage and will continue to select the most optimum solution until it reaches the finish, regardless of whether the answer is the global necessary solution or not. However, it is simple to implement and, in most cases, successful.
Kruskal’s is now a subset of greedy since it is an improved version of the algorithm, and the Greedy Choice is to choose the least weight edge that does not generate a cycle in the MST that has been constructed thus far. We’ll go over it in more depth later in the blog.
Minimum Spanning Tree
A minimal spanning tree (MST) or minimum weight spanning tree for a weighted, linked, undirected graph is a spanning tree with a weight less than or equal to the weight of every other spanning tree.
The weight of a spanning tree is the sum of the weights assigned to each edge of the spanning tree.
If we consider a graph G(V, E), the number of edges necessary for the MST is E=V-1.
Let’s understand Kruskal’s Algorithm more using a graph
Let’s have a look at how Kruskal’s method works using an example. An example will help you grasp Kruskal’s algorithm.
Assume a weighted graph is -
The weight of the aforementioned graph’s edges is shown in the table below -
Now, Sort the above-mentioned edges in increasing order of their weights.
Let’s get started on building the least spanning tree.
Step 1 — To begin, attach the edge AB with weight 1 to the MST.
Step 2 — Because the edge DE with weight 2 is not producing the cycle, add it to the MST.
Step 3 — Because it does not create a cycle or loop, add the edge BC with weight 3 to the MST.
Step 4 — Select the edge CD with weight 4 to the MST since it is not creating the cycle.
Step 5 — Next, select the AE edge with weight 5. Including this edge will result in the cycle, therefore remove it.
Step 6 — Select the AC edge with weight 7. Including this edge will result in the cycle, therefore remove it.
Step 7 — Select the AD edge with weight 10. Including this edge will also result in the cycle, so remove it.
So, using Kruskal’s approach, the final least spanning tree produced from the provided weighted graph is -
The number of edges in the preceding tree now equals the number of vertices minus one. As a result, the algorithm comes to an end here.
Complexity of Kruskal’s algorithm
Let’s look at the time complexity of Kruskal’s algorithm now.
Time Complexity
Kruskal’s algorithm has a temporal complexity of O(E logE) or O(V logV), where E is the number of edges and V is the number of vertices
For Implimentation of Kruskal’s Algorithm Click here…
For Pseudo Code of Kruskal’s Algorithm Click here…
I hope this blog provides sufficient information about Greedy approach and Kruskal’s Algorithm.
Will be back with another such medium blog and a new algorithm.
Stay Tuned!
A Blog by :- Divyansh Palia
