MST Algo: Prim v.s. Kruskal

Minimum Spanning Tree Definition:

1. it connects all nodes in the original graph 2. it has no loop 4. the selected edges has a minimum sum of weights

https://en.wikipedia.org/wiki/Minimum_spanning_tree

Prim and Kruskal are both greedy to find an MST — O(ElogE) But sorting-based Kruskal is more cache-friendly.*

Prim: Next, which node to connect ?

• Start from any node as the 1st node in MST.
• Find the nearest neighbor among selected yellow nodes in O(1) : <Priority Queue / Binary MinHeap>
• Avoid duplicates in MST: Visited Array for nodes

// Min-Heap {weight, node}
priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
vector<bool> visited(n, false);

// select the first node in MST
pq.push({0, start_node}); 
visited[start_node] = true;

// Every edge is checked
while (!pq.empty()) {
    auto [w, u] = pq.top(); pq.pop();       // O(logV)
    if (visited[u]) continue;
    // selected
    visited[u] = true;
    mst_weight += w;

    for (auto& [v, weight] : adj[u]) {
        if (!visited[v]) pq.push({weight, v});
    }
}

• O(E*logE)
• O(E*logV) if heap is modifiable and the heap size is limited to be ≤ V.

Kruskal: Next, which edge to include ?

• Start from the shortest edge as the 1st edge in MST.
• Check the next shortest edge, discard it if including it introduces a loop.
• Pre-Sort the EdgeList in O(E*logE), check whether the two ends of the candidate edge are connected in O(1) : <Union Find>.

sort(edges.begin(), edges.end()); // O(E * log E)

DSU dsu(n);

for (auto& edge : edges) {
    // O(1)
    if (dsu.find(edge.u) != dsu.find(edge.v)) {
        dsu.unite(edge.u, edge.v);
        mst_weight += edge.w;
    }
}

• O(E*logE) : sparse graphs ✅

In the real world implementation, both algorithms are O(E*logE).

But Kruskal is preferred because:

• Sort operation is cache friendly
• while heap swim/sink is easier for a cache miss (the parent and the child are distant in the underlying array).

For very dense graphs where E ≈V², we can use the array-based implementation of Prim’s algorithm (or Prim’s without a heap). This avoids the logarithmic overhead of the heap operations, resulting in O(V²) time complexity.

int u = -1;

// Linear Scan for the nearest neighbor
// O(V)
for (int i = 0; i < V; ++i) {
    if (!visited[i] && (u == -1 || dist[i] < dist[u])) {
        u = i;
    }
}