C++UCS301
Graphs & ApplicationsC++17

Kruskal’s MST

Kruskal considers edges from lightest to heaviest and uses DSU to add only edges that connect different components.

What to understand

  • Edge sorting
  • Cycle avoidance
  • DSU integration
  • Minimum spanning forests

Remember this

  1. 1Sort edges first
  2. 2Add an edge only if representatives differ
  3. 3Naturally handles disconnected graphs as a forest

Detailed notes

Kruskal views the partial solution as a forest. Edges are considered from lightest to heaviest; an edge is safe when its endpoints belong to different components, after which DSU merges them.

The dominant operation is sorting E edges. Kruskal naturally produces a minimum spanning forest on disconnected input and is especially convenient when the graph already arrives as an edge list.

How it works

  1. 1Sort all edges by nondecreasing weight.
  2. 2Find the components of both endpoints.
  3. 3Accept and union only when components differ.
  4. 4For connected input, stop after V−1 accepted edges.

Worked trace

Reject a cycle

Sorted edges: AB=1, BC=2, AC=3, CD=4
  1. 1Accept AB; union A and B.
  2. 2Accept BC; union component AB with C.
  3. 3Reject AC because A and C now share a representative.
  4. 4Accept CD to connect D.
Result: MST edges AB, BC, CD

Where it is used

  • Sparse network design
  • Clustering by removing heavy MST edges
  • Minimum spanning forests

Common mistakes

  • Accepting an edge before checking components
  • Forgetting that MST assumes undirected connectivity
  • Using an inefficient component scan instead of DSU

Complexity analysis

OperationBestAverageWorstExtra space
MSTO(E log E)O(E log E)O(E log E)O(V+E)

C++ implementation

C++17 reference
main.cpp

Kruskal using DSU

Every accepted edge joins two components; stop after V−1 accepted edges for a connected graph.

struct Edge { int from, to, weight; };

long long kruskal(int vertices, vector<Edge> edges) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });
    DSU components(vertices);
    long long total = 0;
    int accepted = 0;
    for (const Edge& edge : edges) {
        if (components.unite(edge.from, edge.to)) {
            total += edge.weight;
            if (++accepted == vertices - 1) break;
        }
    }
    return total;
}
17 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.