Understanding Kruskal’s algorithm

Kruskal’s algorithm is a greedy algorithm, which means that at each step it makes the locally optimal choice, with the hope of finding a global optimum

Kruskal Selects minimum cost edge at every step, but if it forms a cycle, it ignore that edge.

The Kruskal algorithm is a well-known algorithm for finding the minimum spanning tree of a graph. A minimum spanning tree is a subset of the edges of a connected, undirected graph that connects all the vertices together, without any cycles and with the minimum total edge weight.

How it generally works

To implement the Kruskal algorithm, the first step is to sort the edges of the graph by their weight in ascending order. Then, the edges are iteratively added to the minimum spanning tree, starting with the smallest edge and moving to larger edges. At each step, we check if adding the next edge would create a cycle in the current spanning tree. If it would create a cycle, we simply ignore that edge and move on to the next one. If it doesn’t create a cycle, we add it to the minimum spanning tree.

The process continues until all the vertices in the graph are connected in a single tree, at which point the algorithm stops. The resulting tree will be the minimum spanning tree of the original graph.

Let’s understand the working of Kruskal’s algorithm with an example.

Undirected graph with weighted edges

At every iteration, we need to check which one is the minimum edge and also need to check if that node is processed before or not and if it not creating a cycle. if not we can add that to MST(Minimum spanning tree).

• At first, we can see that 1 and 6 are connected with minimum edges weight of 10. we can add those.

• Next minimum edge 12 connecting 3 and 4.

• Next minimum edge is 14 connecting node2 and 7 .

• Next minimum edge is 16 connecting 2 and 3 .

• Next minimum edge is 18 that is connecting 7 and 4 , but it will form a cycle between 7 , 4 , 3 and 2 . So we need to ignore it and check next minimum.
• Next minimum edge is 22 that is connecting 5 and 4 .

• Next minimum edge is 25, that is connecting 6 and 5.

Now, we have processed all the edges and we need to stop the iteration and now we have our minimum spanning tree.

Time Complexity

Time complexity of Kruskal’s algorithm is O (n²). where n is the number if edges. Though, if we use a min Heap that will give us the minimum edge every time then the time complexity is O(n log n). Adding an edge to the minimum spanning tree takes O(1) time.

The Kruskal algorithm can be compared to another well-known algorithm for finding the minimum spanning tree, called the Prim algorithm. The two algorithms are similar in many ways, but the Kruskal algorithm is generally considered to be faster and easier to implement.

The Kruskal algorithm can be generalized to work on directed graphs, and on graphs with negative edge weights. However, for graphs with negative edge weights, it is possible for the Kruskal algorithm to produce a minimum spanning tree that is not unique.

Stay tuned for more to come, If you are new here, do checkout our Algorithms with Javascript blog, we have covered few of the most commonly used algorithms using javascript.