Exploring Time Complexity of Kruskal’s Algorithm in C++

Kruskal's algorithm is a popular algorithm used to find the Minimum Spanning Tree (MST) of a graph.

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

---

How Does Kruskal's Algorithm Work?

Kruskal's algorithm works by:

1. Sorting all edges in non-decreasing order based on their weights.
2. Iteratively selecting the smallest edge that does not form a cycle until all vertices are connected.

vector<Edge> kruskal_mst(vector<Edge>& edges, int vertices_count) {
    // Sort edges based on their weights
    sort(edges.begin(), edges.end(), compare_edge);
 
    // Create Union-Find instance
    UnionFind uf(vertices_count);
 
    vector<Edge> mst; // Output vector to store MST
 
    // Iterate over all the edges
    for (auto& edge : edges) {
        int u = edge.src;
        int v = edge.dest;
 
        // Find the parent of the vertices
        int parent_u = uf.find(u);
        int parent_v = uf.find(v);

        // If the parents are not same,
        // unite them and add the edge to MST
        if (parent_u != parent_v) {
            mst.push_back(edge);
            uf.unite(parent_u, parent_v);
        }
    }
 
    return mst;
}

---

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 of the graph in non-decreasing order of their weights using the sort() function from the C++ Standard Template Library (STL).

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

2. Union-Find Operations

The algorithm uses a Union-Find data structure to keep track of the connected components of the graph.

The time complexity of the Union-Find operations is O(logV) per operation, where V is the number of vertices in the graph.

Thus, the total time complexity of the Union-Find operations is O(E logV) for E edges.

3. Iterating over the Edges

The algorithm iterates over all the edges of the graph to select the smallest edge that does not form a cycle. The time complexity of this operation is O(E).

Overall Time Complexity: O(E logE)

So, the overall time complexity of Kruskal's algorithm is the sum of the time complexities of the three components:

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

The sorting operation dominates the other two components for E greater than V. 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>.

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).