Skip to main content

Exploring Time Complexity of Kruskal’s Algorithm in Python

This article is a complementary resource to the DSA with Python course.

Exploring Time Complexity of Kruskal’s Algorithm in Python

Kruskal's algorithm finds the Minimum Spanning Tree (MST) of a connected, undirected and weighted graph.

In this article, we will analyze the time complexity of a Python implementation of Kruskal's algorithm.


How Does Kruskal's Algorithm Work?

Kruskal's algorithm works by:

  1. Sorting all edges in non-decreasing order of their weights.
  2. Repeatedly picking the smallest edge that does not form a cycle, until all vertices are connected.

To check for cycles quickly, the implementation uses a Union-Find (disjoint set) data structure. Two vertices that already share a root are in the same tree, so an edge between them would form a cycle.

class UnionFind:
    def __init__(self, vertices_count):
        self.parent = list(range(vertices_count))
        self.rank = [0] * vertices_count

    def find(self, vertex):
        # Path compression: point every vertex on the way straight at the root
        if self.parent[vertex] != vertex:
            self.parent[vertex] = self.find(self.parent[vertex])
        return self.parent[vertex]

    def unite(self, root_u, root_v):
        # Union by rank: attach the shorter tree under the taller one
        if self.rank[root_u] < self.rank[root_v]:
            root_u, root_v = root_v, root_u
        self.parent[root_v] = root_u
        if self.rank[root_u] == self.rank[root_v]:
            self.rank[root_u] += 1


def kruskal_mst(edges, vertices_count):
    # Sort edges based on their weights
    edges = sorted(edges, key=lambda edge: edge[2])

    # Create Union-Find instance
    uf = UnionFind(vertices_count)

    mst = []  # Output list to store MST

    # Iterate over all the edges
    for u, v, weight in edges:
        # Find the root of each vertex
        root_u = uf.find(u)
        root_v = uf.find(v)

        # If the roots are not the same,
        # unite them and add the edge to MST
        if root_u != root_v:
            mst.append((u, v, weight))
            uf.unite(root_u, root_v)

    return mst

Here, each edge is a tuple (u, v, weight), and the vertices are numbered from 0 to vertices_count - 1.


Time Complexity

The time complexity of this algorithm can be broken down into the following parts:

1. Sorting the Edges

The algorithm sorts the edges in non-decreasing order of their weights using Python's built-in sorted() function.

The time complexity of this operation is O(E logE), where E is the number of edges in the graph.

2. Union-Find Operations

For every edge, the algorithm calls find() twice and unite() at most once.

Union by rank keeps every tree at most logV levels tall, where V is the number of vertices. So each operation takes at most O(logV) time, and all of them together take at most O(E logV).

Note: Path compression makes the trees even flatter. With both techniques, each operation takes nearly constant time on average, so this part is usually much faster than the bound above.

3. Iterating over the Edges

The loop visits every edge once to decide whether it joins the MST. Apart from the Union-Find calls, the work per edge is constant, so this takes O(E) time.

Overall Time Complexity: O(E logE)

The overall time complexity of Kruskal's algorithm is the sum of the three parts:

O(E logE) + O(E logV) + O(E)

A simple graph has at most V2 edges, so logE is at most 2logV. That makes O(E logV) no larger than O(E logE), and sorting dominates. Therefore, the algorithm's overall complexity is O(E logE).


Factors Affecting the Time Complexity

1. Dense Graph

In a dense graph, the number of edges E is close to the square of the number of vertices V.

Therefore, the overall time complexity is <katex>O(V^{2} logV)</katex>.

A Complete Graph is an Example of a Dense Graph
A Complete Graph is an Example of a Dense Graph

Note: The time complexity should actually be <katex>O(V^{2} logV^{2})</katex>. Using the logarithmic property, it becomes <katex>O(V^{2} * 2logV)</katex>. We simply neglect the constant 2 to obtain <katex>O(V^{2} logV)</katex>.

2. Sparse Graph

In a sparse graph, the number of edges E is close to the number of vertices V.

Therefore, the overall time complexity is O(V logV).