Minimum Spanning Tree Kruskal's Algorithm in DSA C

Mental Model

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

Analogy: Imagine connecting cities with roads. You want to build the cheapest roads so every city is reachable, but you never build a road that creates a circle of roads.

Vertices: A B C D
Edges:
A --2-- B
B --3-- C
A --1-- C
C --4-- D

Initial: No roads built
A B C D

Goal: Connect all with cheapest roads without loops

Dry Run Walkthrough

Input: Graph with vertices A, B, C, D and edges: A-C(1), A-B(2), B-C(3), C-D(4)

Goal: Build a tree connecting all vertices with minimum total edge weight without cycles

Step 1: Sort edges by weight: A-C(1), A-B(2), B-C(3), C-D(4)

Edges sorted: [A-C(1), A-B(2), B-C(3), C-D(4)]

Why: We pick edges from smallest to largest to keep total cost low

Step 2: Pick edge A-C(1), add to MST

MST edges: A-C(1)
Connected sets: {A,C}, {B}, {D}

Why: First smallest edge connects two separate sets

Step 3: Pick edge A-B(2), add to MST

MST edges: A-C(1), A-B(2)
Connected sets: {A,B,C}, {D}

Why: Edge connects B to existing set without cycle

Step 4: Consider edge B-C(3), skip because it forms a cycle in {A,B,C}

MST edges: A-C(1), A-B(2)
Connected sets: {A,B,C}, {D}

Why: Adding this edge would create a loop

Step 5: Pick edge C-D(4), add to MST

MST edges: A-C(1), A-B(2), C-D(4)
Connected sets: {A,B,C,D}

Why: Connects last vertex D without cycle

Result:

MST edges: A-C(1) -> A-B(2) -> C-D(4)
All vertices connected with minimum total cost 7

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX_EDGES 100
#define MAX_VERTICES 100

// Edge structure
typedef struct {
    int src, dest, weight;
} Edge;

// Disjoint Set Union (Union-Find) structure
int parent[MAX_VERTICES];

// Find root parent with path compression
int find(int i) {
    if (parent[i] != i)
        parent[i] = find(parent[i]); // compress path
    return parent[i];
}

// Union two sets
void union_sets(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        parent[rootB] = rootA; // attach rootB to rootA
    }
}

// Compare function for qsort to sort edges by weight
int compare(const void* a, const void* b) {
    Edge* e1 = (Edge*)a;
    Edge* e2 = (Edge*)b;
    return e1->weight - e2->weight;
}

// Kruskal's algorithm
void kruskal(Edge edges[], int E, int V) {
    // Initialize disjoint sets
    for (int i = 0; i < V; i++) {
        parent[i] = i;
    }

    // Sort edges by weight
    qsort(edges, E, sizeof(Edge), compare);

    printf("Edges in MST:\n");
    int mst_weight = 0;
    int count = 0;

    for (int i = 0; i < E && count < V - 1; i++) {
        int u = edges[i].src;
        int v = edges[i].dest;

        // Check if adding this edge creates a cycle
        if (find(u) != find(v)) {
            union_sets(u, v); // union sets
            printf("%c - %c : %d\n", 'A' + u, 'A' + v, edges[i].weight);
            mst_weight += edges[i].weight;
            count++;
        }
    }
    printf("Total MST weight: %d\n", mst_weight);
}

int main() {
    // Vertices: A=0, B=1, C=2, D=3
    int V = 4;
    int E = 4;
    Edge edges[] = {
        {0, 2, 1}, // A-C
        {0, 1, 2}, // A-B
        {1, 2, 3}, // B-C
        {2, 3, 4}  // C-D
    };

    kruskal(edges, E, V);
    return 0;
}

for (int i = 0; i < V; i++) { parent[i] = i; }

Initialize each vertex as its own set

qsort(edges, E, sizeof(Edge), compare);

Sort edges by weight ascending

if (find(u) != find(v)) {

Check if edge connects two different sets to avoid cycles

union_sets(u, v);

Merge sets after adding edge to MST

printf("%c - %c : %d\n", 'A' + u, 'A' + v, edges[i].weight);

Print edge added to MST

Output

Edges in MST:

A - C : 1

A - B : 2

C - D : 4

Total MST weight: 7

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 edges and parent array for union-find

vs Alternative: Compared to Prim's algorithm which can be O(E + V log V) with priority queue, Kruskal is simpler and efficient for sparse graphs

Edge Cases

Empty graph (no edges)

No edges to add, MST is empty

DSA C

for (int i = 0; i < E && count < V - 1; i++) {

Graph with single vertex

No edges needed, MST weight is zero

DSA C

for (int i = 0; i < V; i++) { parent[i] = i; }

Graph with multiple edges of same weight

Algorithm picks edges in sorted order, ties resolved by qsort order

DSA C

qsort(edges, E, sizeof(Edge), compare);

When to Use This Pattern

When you need to connect all points with minimum total cost and avoid cycles, use Kruskal's algorithm because it picks edges from smallest to largest and uses union-find to detect cycles.

Common Mistakes

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

Mistake: Not sorting edges by weight before processing
Fix: Sort edges ascending by weight before starting to pick edges

Summary

Builds a minimum cost tree connecting all vertices without cycles by picking edges from smallest to largest.

Use when you want the cheapest way to connect all points and have the graph edges available upfront.

The key insight is to add edges in order of weight and skip those that form cycles using union-find.

Practice

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

easy

A. To sort the vertices of a graph

B. To find the shortest path between two nodes

C. To detect cycles in a graph

D. To find the minimum spanning tree of a graph

Solution

1. Step 1: Understand Kruskal's algorithm purpose

   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 focuses on building a minimum spanning tree.

3. Final Answer:

   To find the minimum spanning tree of a graph -> Option D

4. Quick Check:

   Kruskal's algorithm = Minimum Spanning Tree [OK]

Hint: Kruskal's always builds minimum spanning tree by edges [OK]

Common Mistakes:

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

2. Which data structure is commonly used in Kruskal's algorithm to detect cycles efficiently?

easy

A. Disjoint Set (Union-Find)

B. Stack

C. Queue

D. Priority Queue

Solution

1. Step 1: Identify cycle detection method in Kruskal's

   Kruskal's algorithm uses a Disjoint Set (Union-Find) data structure to check if adding an edge creates a cycle by checking if two vertices belong to the same set.

2. Step 2: Compare other data structures

   Queue and stack do not help detect cycles efficiently here; priority queue is used for sorting edges but not cycle detection.

3. Final Answer:

   Disjoint Set (Union-Find) -> Option A

4. Quick Check:

   Cycle detection in Kruskal's = Union-Find [OK]

Hint: Use Union-Find to quickly check cycles in Kruskal's [OK]

Common Mistakes:

• Confusing priority queue with cycle detection
• Using stack or queue for cycle detection
• Not knowing Union-Find purpose

3. Consider the following edges of a graph with weights:
Edges = [(A-B, 1), (B-C, 4), (A-C, 3), (C-D, 2)]
What is the total weight of the minimum spanning tree found by Kruskal's algorithm?

medium

A. 7

B. 6

C. 8

D. 10

Solution

1. Step 1: Sort edges by weight

   Sorted edges: (A-B,1), (C-D,2), (A-C,3), (B-C,4)

2. Step 2: Pick edges without cycles

   Pick (A-B,1), then (C-D,2), then (A-C,3). Adding (B-C,4) creates a cycle, so skip it.

3. Step 3: Calculate total weight

   Total weight = 1 + 2 + 3 = 6

4. Final Answer:

   6 -> Option B

5. Quick Check:

   Sum of MST edges = 6 [OK]

Hint: Sort edges, pick smallest without cycle until all connected [OK]

Common Mistakes:

• Adding all edges without checking cycles
• Choosing edges in wrong order
• Miscounting total weight

4. The following C code snippet is part of Kruskal's algorithm. What is the error?

int findParent(int parent[], int i) {
    if (parent[i] == i)
        return i;
    return findParent(parent, parent[i]);
}

void unionSet(int parent[], int x, int y) {
    int xset = findParent(parent, x);
    int yset = findParent(parent, y);
    parent[xset] = yset;
}

medium

A. unionSet should swap xset and yset

B. unionSet should not change parent array

C. Missing path compression in findParent

D. findParent should return void

Solution

1. Step 1: Analyze findParent function

   findParent recursively finds the root parent but does not update parent[i] to root, missing path compression optimization.

2. Step 2: Understand unionSet function

   unionSet correctly merges sets by updating parent of one root to another; no swap needed.

3. Final Answer:

   Missing path compression in findParent -> Option C

4. Quick Check:

   Path compression missing = findParent optimization [OK]

Hint: Add path compression to speed up findParent [OK]

Common Mistakes:

• Thinking unionSet must swap parents
• Believing findParent should return void
• Ignoring path compression importance

5. Given a graph with vertices {1, 2, 3, 4} and edges with weights:
(1-2, 5), (1-3, 3), (2-3, 4), (2-4, 2), (3-4, 7)
Using Kruskal's algorithm, which edges will be included in the minimum spanning tree?

hard

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

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

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

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

Solution

1. Step 1: Sort edges by weight

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

2. Step 2: Pick edges without cycles

   Pick (2-4,2), then (1-3,3). Next (2-3,4) connects 2 and 3 which are in different sets, so pick it. After these three edges, all vertices are connected and MST is complete.

3. Step 3: Verify options

   (2-4), (1-3), (2-3) matches edges (2-4), (1-3), (2-3). (2-4), (1-3), (1-2) includes (1-2) which is heavier than (2-3), so incorrect.

4. Final Answer:

   (2-4), (1-3), (2-3) -> Option A

5. Quick Check:

   Pick smallest edges connecting all vertices without cycle [OK]

Hint: Sort edges, pick smallest connecting new vertices until all connected [OK]

Common Mistakes:

• Choosing heavier edges over lighter ones
• Adding edges that create cycles
• Not stopping after n-1 edges