Chapter 76

Home

Minimum Spanning Tree: Kruskal

A spanning tree connects all V nodes with V−1 edges. Kruskal's algorithm finds the one with minimum total weight: sort edges, greedily add the lightest edge that doesn't form a cycle.

Kruskal's Algorithm

Sort edges by weight. Then iterate: if adding edge (u,v) doesn't create a cycle (u and v are in different components), add it. Repeat until V−1 edges are added.

C++ — Kruskal with cycle-check via DFS (slow)

struct Edge { int u, v, w; };

int kruskal_naive(vector& edges, int V) {
    sort(edges.begin(), edges.end(),
         [](auto& a, auto& b) { return a.w < b.w; });

    vector> tree(V);  // current MST
    int total = 0, added = 0;

    for (auto& e : edges) {
        // Check if u and v are already connected in tree
        // via DFS — O(V) per edge!
        if (are_connected(tree, e.u, e.v)) continue;

        tree[e.u].push_back(e.v);
        tree[e.v].push_back(e.u);
        total += e.w;
        added++;
        if (added == V - 1) break;
    }
    return total;
}

// O(E × V) — too slow for large graphs

🚨 DFS-based cycle check is O(V) per edge

Running DFS to check connectivity each time makes Kruskal O(E×V). Union-Find (next chapter) reduces cycle-check to near-O(1) per edge.

Key Takeaways