Kruskal's Minimum Spanning Tree Algorithm

Kruskal’s algorithm is a graph based algorithm which is used to build Minimum Spanning Tree (MST) for a given weighted, undirected graph. It creates MST by greedily adding the cheapest available edge to the tree, as long as it does not create a cycle. The algorithm starts by sorting all the edges in the graph in ascending order of their weights. Then, it iterates through the sorted edges and adds each edge to the MST if it does not create a cycle. The algorithm continues until all the vertices are connected, forming the MST.

What is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that connects all the vertices together with the minimum possible total edge weight. In other words, it is the cheapest or minimum cost subgraph in a given graph that connects all the nodes in the graph.

For example, for the undirected weighted graph shown below:

Below is how the minimum spanning tree looks like:

Refer to this article to learn more about Minimum Spanning Trees.

Detailed Steps of Kruskal’s MST Algorithm

Below are the steps involved in Kruskal’s algorithm to find Minimum Spanning Tree (MST) of an undirected and weighted graph:

Preliminary Step: Representation of Graph

• Represent the graph as a list of edges, where each edge is a tuple (u, v, w) representing a connection between vertices u and v with weight w.

Step 1: Edge Sorting

• Sort all edges in the graph in ascending order based on their weights.

Step 2: Initialization of Data Structure For Detecting Cycles

• Create a disjoint set data structure to keep track of connected components.
• This data structure is used to check if addition of an edge to the MST will cause any cycles. In other words, this data structure is used to find if the two nodes involved with the current edge are already part of the same set/component.
• We use union-find algorithm for merging two nodes into a single component/set while adding an edge to the MST
• Initially, each vertex is in its own component.

Step 3: Edge Selection and Component Merging

• Iterate through the sorted edges:
  • For each edge (u, v, w), determine if vertices u and v belong to different components.
  • If they are in different components:
    • Add this edge to the minimum spanning tree.
    • Merge the components containing u and v in the disjoint set data structure.
  • If they are in the same component, discard this edge to avoid creating a cycle.

Step 4: Termination

• Continue Step 3 until either:
  • All vertices are in the same component (indicating a fully connected MST), or
  • All edges have been processed.

The final result is the minimum spanning tree, which is a subgraph of the original graph that connects all vertices with the minimum total weight of the edges.

Implementation of Kruskal’s Algorithm

Time & Space Complexity

Time Complexity

The time complexity of Kruskal’s algorithm for finding Minimum Spanning Tree in a graph is O(E log E), where E is the number of edges present in the graph.

The reason for this time complexity is as follows:

• Sorting the edges: The first step of Kruskal’s algorithm is to sort the edges in ascending order of their weights. This step takes O(E log E) time.
• Checking for cycles: As the algorithm progresses, it checks whether adding an edge to the MST would create a cycle. This is done using a data structure called a disjoint-set (or union-find) data structure, which allows for efficient checking of whether two vertices are in the same connected component. Efficient implementations of disjoint-set data structure brings the overall time complexity of this step to O(E).
• Adding edges to the MST: The final step is to add the edges to the MST. This can be done in O(1) time per edge, as it involves appending the edge to the end of MST array.

Combining these steps, the overall time complexity of Kruskal’s algorithm is O(E log E).

Space Complexity

The space complexity of Kruskal’s algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

The reason for this space complexity is as follows:

• Storing the graph: The algorithm needs to sort and store all edges in the graph, which requires O(E) space.
• Storing the disjoint-set data structure: The algorithm uses a disjoint-set data structure to keep track of the connected components in the graph. This data structure requires O(V) space to store the parent information for each vertex.

Combining these space requirements, the overall space complexity of Kruskal’s algorithm is O(V + E).