Q16Data Structures

A Minimum Spanning Tree (MST) of a weighted, connected, undirected graph is a strict acyclic subgraph that systematically connects all constituent vertices together while mathematically ensuring the aggregate total of its edge weights is the absolute minimum possible.

Differentiating the Algorithmic Approaches

Both Kruskal's and Prim's algorithms employ greedy logic to construct an MST, but their fundamental architectural approaches to graph exploration are entirely distinct:

• Kruskal's Algorithm (Edge-Centric): Kruskal's algorithm fundamentally views the graph strictly as a vast collection of independent edges. It begins by aggressively sorting all edges globally by weight. It then iteratively builds a "forest" of disconnected trees by greedily selecting the absolute cheapest edge anywhere in the graph, merging disjoint trees together, provided the new edge does not introduce a structural cycle (managed via a Union-Find data structure). It is highly optimal for sparse graphs.
• Prim's Algorithm (Vertex-Centric): Prim's algorithm operates completely differently. It selects a single, arbitrary starting vertex and views the MST as a single, continuously expanding connected entity. It iteratively expands this unified tree by scanning all edges that connect the current tree to any unvisited vertex, and greedily pulling in the absolutely cheapest connecting edge. It is highly optimal for dense, highly connected graphs.

Time Complexity Analysis

The architectural differences lead to distinct computational time complexities based heavily on their underlying implementation structures:

• Kruskal's Complexity: The dominating factor is the initial global sorting of all $E$ edges. Utilizing efficient algorithms like Merge Sort, this strictly bounds the overall time complexity to $O(E\log E)$ or equivalently $O(E\log V)$.
• Prim's Complexity: The efficiency of Prim's relies entirely on the data structure managing the expanding frontier. Using a simple Adjacency Matrix yields a sluggish $O(V^2)$. However, utilizing an Adjacency List paired with a highly optimized Binary Min-Heap (Priority Queue) drastically reduces the time complexity to an exceptionally fast $O(E\log V)$, making it superior for dense networks where $E\approx V^2$.