Kruskal’s Algorithm using Greedy method

Introduction

When we hear the word algorithm, it gives us an idea of problem-solving. That’s what it is. An algorithm is a step-by-step process of solving a task. Every task that we perform in our day-to-day lives, contains an algorithm for its solution. It is not a complete program or code; rather, it is a solution (logic) to a problem that may be stated informally using a Flowchart or Pseudocode. In the context of Design Analysis and Algorithms (DAA), Kruskal’s Algorithm is one of them.

Kruskal’s Algorithm

Before we jump directly into the algorithm, let’s discuss what is a spanning tree. A spanning tree is a subgraph of that graph that is a tree that connects all the vertices. For a weighted, connected, undirected graph, a minimum spanning tree (MST) or minimum weight spanning tree is a spanning tree with a weight less than or equal to the weight of every other spanning tree. It satisfies the following conditions:

1. It should have the same number of vertices as there are in the graph.

2. It should have (V-1) number of edges, where V = number of vertices.

3. It should be acyclic.

If the selected edges do not form any cycle, Kruskal’s algorithm arranges them in increasing order and continues to build nodes. The node with the lowest cost is chosen first, followed by the node with the highest cost.

Let’s understand this through an example!

Suppose we are given a weighted graph:

Image from Javatpoint

The weight of the edges of the above graph is given in the below table –

Table from Javatpoint

Now, we’ll sort the edges given above in the ascending order of their weights.

Table from Javatpoint

Now, let’s start constructing the minimum spanning tree.

Step 1 — First, add the edge AB with weight 1 to the MST.

Image from Javatpoint

Step 2 — Add the edge DE with weight 2 to the MST as it is not creating the cycle.

Image from Javatpoint

Step 3 — Add the edge BC with weight 3 to the MST, as it is not creating any cycle or loop.

Image from Javatpoint

Step 4 — Now, pick the edge CD with weight 4 to the MST, as it is not forming the cycle.

Image from Javatpoint

Step 5 — After that, pick the edge AE with weight 5. Including this edge will create the cycle, so discard it.

Step 6 — Pick the edge AC with weight 7. Including this edge will create the cycle, so discard it.

Step 7 — Pick the edge AD with weight 10. Including this edge will also create the cycle, so discard it.

So, the final minimum spanning tree obtained from the given weighted graph by using Kruskal’s algorithm is -

Image from Javatpoint

The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Now, the number of edges in the above tree equals the number of vertices minus 1. So, we’ll stop the algorithm here.

Algorithm

1. Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree.
2. Step 2: Create a set E that contains all the edges of the graph.
3. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning
4. Step 4: Remove an edge from E with minimum weight
5. Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F
6. (for combining two trees into one tree).
7. ELSE
8. Discard the edge
9. Step 6: END

Time Complexity

Because sorting edges requires O(ElogE) time, the time complexity of this technique is O(ElogE) or O(ElogV). After sorting, we run the find-union algorithm over and over again, which takes O(logV) time. As a result, the total time consumed is now O(ElogE+ElogV), and the overall time complexity is either O(ElogE) or O(ElogV).

That’s all which was needed to know about Kruskal’s Algorithm. Thanks for reading!