Q12Discrete Mathematics

In computational graph theory, Kruskal's Algorithm is a highly renowned, greedy mathematical procedure explicitly engineered to discover the Minimum Spanning Tree (MST) for a connected, undirected, and edge-weighted graph. A Spanning Tree is a crucial subgraph that physically connects every single vertex together without ever forming any closed loops (cycles). A Minimum Spanning Tree is the specific spanning tree whose total sum of edge weights is the absolute lowest possible value.

Algorithmic Methodology

Kruskal's algorithm operates on a strictly global, greedy heuristic, prioritizing edges globally across the entire graph rather than growing locally from a specific vertex.

• Step 1: Global Sorting. The algorithm initiates by aggressively extracting every single edge from the graph. It then mathematically sorts this entire list of edges in strictly ascending order based exclusively on their assigned weights (from the absolute cheapest edge to the most expensive).
• Step 2: Initialization. The algorithm creates an empty edge set, $T$, which will ultimately hold the final Minimum Spanning Tree. Initially, it treats every single vertex in the graph as its own isolated, independent tree (a forest of singular nodes).
• Step 3: Greedy Iteration. The algorithm sequentially evaluates the sorted edge list, starting with the very first (cheapest) edge.
• Step 4: Cycle Detection. Before physically adding an edge to the growing tree $T$, the algorithm must rigorously verify that connecting this edge will not mathematically create a closed loop (a cycle) among the edges already existing in $T$. This is almost universally implemented utilizing a highly efficient "Disjoint-Set" (Union-Find) data structure. If the two endpoints of the candidate edge already belong to the exact same connected component within $T$, adding the edge would trigger a fatal cycle, and the edge is immediately permanently discarded.
• Step 5: Edge Inclusion. If adding the candidate edge does not form a cycle (its endpoints belong to two completely separate components), the edge is officially added to $T$. The two formerly separate components are then mathematically merged (Union) into a single, larger connected component.
• Step 6: Termination. The iterative evaluation continues until the tree $T$ contains exactly $V-1$ edges (where $V$ is the total number of vertices in the original graph). Once this mathematical threshold is achieved, the graph is fully spanned, and the algorithm instantaneously terminates.

Algorithmic Complexity

The overall time complexity is heavily dominated by the initial sorting of the edges. For $E$ edges and $V$ vertices, sorting requires $O(E\log E)$ time. The subsequent Union-Find operations take near-constant time. Thus, the total operational complexity is mathematically bounded by $O(E\log E)$ or equivalently $O(E\log V)$.