Introduction

Kruskal's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph with weighted edges. Named after Joseph Kruskal, it is one of the most popular algorithms in graph theory and is often used in network design and other applications. A central aspect of evaluating the efficiency of this algorithm lies in understanding its time complexity.

Basics of Kruskal's Algorithm

To execute Kruskal's algorithm, follow these general steps:

1. Sort all the edges in non-decreasing order of their weight.
2. Initialize a forest with (n) trees, each containing one of the (n) vertices.
3. Iteratively add edges in increasing order of their weight, ensuring that no cycles are formed by adding an edge. If adding an edge creates a cycle, discard that edge.
4. Repeat step 3 until there are (n-1) edges in the forest (which will now become a single tree).

Time Complexity Analysis

The time complexity of the Kruskal algorithm is determined by the following steps:

1. Sorting the Edges

Sorting the edges is the most computationally expensive operation in the Kruskal algorithm. Given E edges, a typical sorting algorithm such as Merge Sort or Python's sorted() function has a complexity of $O(E \log E)$.

2. Creating a Forest

Creating a forest with a separate tree for each vertex is straightforward. This operation is O(V) , where V is the number of vertices.

3. Union-Find Operations

Union-Find (or Disjoint Set Union, DSU) is used to efficiently manage the connected components and check for cycle formation. If implemented with path compression and union by rank, the operations find and union can be performed in near constant time, given by $O(\alpha(V))$, where $\alpha$ is the inverse Ackermann function, making its time complexity almost $O(1)$ for most practical purposes.

The total time complexity for performing these operations over all E edges is $O(E \alpha(V))$.

Summary

Given the steps above, the overall time complexity of Kruskal's algorithm is dominated by the sorting step:

$$O(E \log E + E \alpha(V)) \approx O(E \log E)$$

This is because $O(E \log E)$ will significantly surpass $O(E \alpha(V))$ for large graphs.

Example

Let's look at a simple example graph to illustrate Kruskal's algorithm:

4 | 5 |