Kruskal’s Minimum Spanning Tree Algorithm.

Kruskal’s Algorithm falls under Greedy Algorithms which are mainly used in calculating MST or minimum spanning tree. So let’s discuss spanning tree before we move on to the algorithm.

Spanning Tree

The Spanning Tree can be defined as the subset of a graph, covering all vertices and should be acyclic. The Spanning tree cannot be cyclic and it cannot be disconnected.

Spanning Trees

Minimum Spanning Tree

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all of the vertices together, with none cycles and with the minimum viable overall edge weight.

Kruskal’s Algorithm

This algorithm falls under the class of algorithms Greedy Algorithm that find the optimum cost.

Steps:

1. Firstly sort all the edges with their respective cost in an ascending order, that is from lowest to highest.
2. After that mark all the vertices in the spanning tree as shown in the original diagram.
3. Then locate the edge with the lowest cost and add it to the spanning tree. For example if an edge connecting vertices 2 & 3 has the lowest cost i.e. 1 then we add that edge to the spanning tree.
4. Now continue this process and make sure that if connecting a particular edge leads to creating a cycle then reject that edge and move on to the next one.
5. We keep on adding edges to the spanning trees until all the vertices are interconnected.

Kruskal Example 1

Kruskal Example 2

Time Complexity:

Kruskal’s algorithm time complexity is O(ElogV) where E is edges and V is vertices, it is so because it includes sorting of edges.

Applications:

• Laying out electrical wiring
• Computer networks (LAN connection)