Minimum Spanning Tree Kruskal's Algorithm in DSA C++

Mental Model

Pick the smallest edges one by one to connect all points without making loops.

Analogy: Imagine building roads between cities by always choosing the cheapest road that doesn't create a circle of roads.

Graph:
  (1)---2---(2)
   |         |
   3         1
   |         |
  (3)---4---(4)

Edges with weights: 1-2:2, 1-3:3, 2-4:1, 3-4:4

Dry Run Walkthrough

Input: Graph with nodes 1,2,3,4 and edges: (1-2,2), (1-3,3), (2-4,1), (3-4,4)

Goal: Find the minimum set of edges connecting all nodes with the smallest total weight and no cycles.

Step 1: Sort edges by weight: (2-4,1), (1-2,2), (1-3,3), (3-4,4)

Edges sorted: (2-4,1) -> (1-2,2) -> (1-3,3) -> (3-4,4)

Why: We pick edges starting from the smallest weight to keep total cost low.

Step 2: Pick edge (2-4,1), add to MST since it connects two different sets

MST edges: (2-4,1)
Sets: {1}, {2,4}, {3}

Why: No cycle formed, so we add the smallest edge.

Step 3: Pick edge (1-2,2), add to MST since it connects different sets {1} and {2,4}

MST edges: (2-4,1), (1-2,2)
Sets: {1,2,4}, {3}

Why: Still no cycle, connecting more nodes.

Step 4: Pick edge (1-3,3), add to MST since it connects {1,2,4} and {3}

MST edges: (2-4,1), (1-2,2), (1-3,3)
Sets: {1,2,3,4}

Why: All nodes connected, MST complete.

Step 5: Skip edge (3-4,4) because it connects nodes already in the same set, would form a cycle

MST edges unchanged: (2-4,1), (1-2,2), (1-3,3)

Why: Avoid cycles to keep MST property.

Result:

MST edges: (2-4,1) -> (1-2,2) -> (1-3,3)
Total weight: 6

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

class DisjointSet {
    vector<int> parent, rank;
public:
    DisjointSet(int n) {
        parent.resize(n+1);
        rank.resize(n+1, 0);
        for (int i = 1; i <= n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false; // same set, would form cycle
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
};

int main() {
    int n = 4; // nodes
    vector<Edge> edges = {
        {1, 2, 2},
        {1, 3, 3},
        {2, 4, 1},
        {3, 4, 4}
    };

    sort(edges.begin(), edges.end()); // sort edges by weight

    DisjointSet ds(n);
    vector<Edge> mst;
    int total_weight = 0;

    for (auto& e : edges) {
        if (ds.unite(e.u, e.v)) { // add edge if no cycle
            mst.push_back(e);
            total_weight += e.weight;
        }
    }

    for (auto& e : mst) {
        cout << "(" << e.u << "-" << e.v << "," << e.weight << ") ";
    }
    cout << "\nTotal weight: " << total_weight << endl;

    return 0;
}

sort(edges.begin(), edges.end());

sort edges by weight ascending to pick smallest first

if (ds.unite(e.u, e.v)) {

add edge only if it connects two different sets (no cycle)

mst.push_back(e);

include edge in MST

total_weight += e.weight;

accumulate total MST weight

Output

(2-4,1) (1-2,2) (1-3,3) 

Total weight: 6

Complexity Analysis

Time: O(E log E) because sorting edges dominates and union-find operations are almost O(1)

Space: O(V + E) for storing disjoint sets and edges

vs Alternative: Compared to Prim's algorithm, Kruskal's is simpler for sparse graphs and uses sorting edges instead of priority queues.

Edge Cases

Empty graph (no edges)

No MST edges, total weight zero

DSA C++

for (auto& e : edges) { if (ds.unite(e.u, e.v)) {

Graph with one node

No edges to add, MST is empty

DSA C++

for (auto& e : edges) { if (ds.unite(e.u, e.v)) {

Graph with multiple edges having same weight

Algorithm picks edges in sorted order, ties broken by input order, still no cycles

DSA C++

sort(edges.begin(), edges.end());

When to Use This Pattern

When you need to connect all points with minimum total cost and no loops, and edges have weights, reach for Kruskal's algorithm using sorting and union-find.

Common Mistakes

Mistake: Not checking if adding an edge creates a cycle before adding it.
Fix: Use union-find to check if two nodes belong to different sets before adding the edge.

Mistake: Not sorting edges by weight before processing.
Fix: Sort edges ascending by weight to ensure smallest edges are chosen first.

Summary

Finds the minimum total weight set of edges connecting all nodes without cycles.

Use when you have a weighted graph and want the cheapest way to connect all points.

Sort edges by weight and add them if they don't form a cycle, using union-find to check.

Practice

1. What is the main goal of Kruskal's Algorithm in graph theory?

easy

A. To find the minimum spanning tree of a connected weighted graph

B. To find the shortest path between two nodes

C. To detect cycles in a graph

D. To sort the vertices of a graph

Solution

1. Step 1: Understand the purpose of Kruskal's Algorithm

   Kruskal's Algorithm is designed to find a subset of edges that connects all vertices with the minimum total edge weight and no cycles.

2. Step 2: Compare with other graph algorithms

   Unlike shortest path or cycle detection, Kruskal's specifically builds a minimum spanning tree.

3. Final Answer:

   To find the minimum spanning tree of a connected weighted graph -> Option A

4. Quick Check:

   Minimum Spanning Tree = Find minimum edges connecting all nodes [OK]

Hint: Kruskal connects all nodes with least total edge weight [OK]

Common Mistakes:

• Confusing MST with shortest path
• Thinking it detects cycles only
• Assuming it sorts vertices

2. Which of the following is the correct way to sort edges by weight in C++ for Kruskal's Algorithm?

easy

A. std::sort(edges.begin(), edges.end(), [](auto &a, auto &b){ return a.weight < b.weight; });

B. std::sort(edges, edges + n, [](auto a, auto b){ return a.weight > b.weight; });

C. sort(edges.begin(), edges.end(), compareEdges); // where compareEdges returns a.weight > b.weight

D. edges.sort([](auto a, auto b){ return a.weight < b.weight; });

Solution

1. Step 1: Identify correct sorting syntax for vector of edges

   Using std::sort with iterators edges.begin() and edges.end() is correct for vectors.

2. Step 2: Check lambda comparator correctness

   The comparator should return true if first edge weight is less than second for ascending order.

3. Final Answer:

   std::sort(edges.begin(), edges.end(), [](auto &a, auto &b){ return a.weight < b.weight; }); -> Option A

4. Quick Check:

   Sort edges ascending by weight using std::sort with correct lambda [OK]

Hint: Use std::sort with begin/end and lambda returning a.weight < b.weight [OK]

Common Mistakes:

• Using wrong iterator syntax for vector
• Reversing comparator logic
• Calling sort on vector object directly

3. Given the following edges of a graph:
edges = { {1, 2, 3}, {2, 3, 1}, {1, 3, 2} } where each tuple is (u, v, weight).
What is the total weight of the MST found by Kruskal's Algorithm?

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Sort edges by weight

   Sorted edges by weight: (2,3,1), (1,3,2), (1,2,3)

2. Step 2: Pick edges without forming cycles

   Pick (2,3,1), then (1,3,2). Adding (1,2,3) forms a cycle, so skip.

3. Final Answer:

   1 + 2 = 3 -> Option C

4. Quick Check:

   Sum of selected edges = 1 + 2 = 3 [OK]

Hint: Pick edges from smallest weight, skip if cycle forms [OK]

Common Mistakes:

• Adding all edges without checking cycles
• Choosing edges in wrong order
• Misreading edge weights

4. Consider this snippet for Kruskal's Algorithm union-find step:

if (find(u) != find(v)) {
  unionSet(u, v);
  mst_weight += w;
}

What is the likely error if the MST weight is incorrect?

medium

A. Union operation is called before checking if sets are different

B. The find function does not use path compression

C. The unionSet function does not update parent correctly

D. Edges are not sorted by weight before processing

Solution

1. Step 1: Analyze union-find usage

   The code correctly checks if u and v belong to different sets before union and adding weight.

2. Step 2: Check prerequisites for Kruskal's correctness

   Kruskal requires edges sorted by weight ascending before processing; missing this causes incorrect MST weight.

3. Final Answer:

   Edges are not sorted by weight before processing -> Option D

4. Quick Check:

   Sorting edges first is essential for correct MST [OK]

Hint: Always sort edges by weight before union-find steps [OK]

Common Mistakes:

• Ignoring edge sorting
• Assuming union-find alone fixes MST
• Confusing path compression with correctness

5. You have a graph with 5 nodes and edges:
{(1,2,2), (1,3,3), (2,3,1), (2,4,4), (3,5,5), (4,5,7)}
Using Kruskal's Algorithm, which edges will be included in the MST?

hard

A. {(2,3,1), (1,3,3), (2,4,4), (4,5,7)}

B. {(2,3,1), (1,2,2), (2,4,4), (3,5,5)}

C. {(1,2,2), (1,3,3), (3,5,5), (4,5,7)}

D. {(1,3,3), (2,3,1), (4,5,7), (2,4,4)}

Solution

1. Step 1: Sort edges by weight

   Sorted edges: (2,3,1), (1,2,2), (1,3,3), (2,4,4), (3,5,5), (4,5,7)

2. Step 2: Pick edges without cycles

   Pick (2,3,1), (1,2,2), (2,4,4), (3,5,5). Adding (1,3,3) or (4,5,7) creates cycles.

3. Final Answer:

   {(2,3,1), (1,2,2), (2,4,4), (3,5,5)} -> Option B

4. Quick Check:

   Edges chosen connect all nodes with minimum total weight [OK]

Hint: Pick edges by ascending weight, skip if cycle forms [OK]

Common Mistakes:

• Including edges that form cycles
• Not sorting edges before selection
• Missing edges needed to connect all nodes