Minimum Spanning Tree Kruskal's Algorithm in DSA C - Build from Scratch

Minimum Spanning Tree using Kruskal's Algorithm

📖 Scenario: You are working as a network engineer. You need to connect several computers with cables. Each cable has a cost. Your goal is to connect all computers with the least total cost, without any loops.

🎯 Goal: Build a program in C that uses Kruskal's algorithm to find the minimum spanning tree (MST) of a given graph. The program will show which connections (edges) to use and the total cost.

📋 What You'll Learn

Create an array of edges with given weights

Create a helper array for union-find operations

Implement Kruskal's algorithm to select edges for MST

Print the edges in the MST and the total cost

💡 Why This Matters

🌍 Real World

Network design to connect computers or cities with minimum cable cost.

💼 Career

Useful for software engineers working on network optimization, infrastructure planning, or graph algorithms.

1

Create the graph edges array

Create a struct called Edge with int src, int dest, and int weight. Then create an array called edges with these 5 edges: (0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4).

DSA C

// Define struct Edge and create edges array with 5 edges
// Your code here

Hint

Use typedef struct to define Edge. Then create an array edges with 5 elements using the given values.

2

Create union-find helper arrays

Create two integer arrays called parent and rank of size 4. Initialize parent so that each element is its own parent (0 to 3). Initialize all elements of rank to 0.

DSA C

typedef struct {
    int src;
    int dest;
    int weight;
} Edge;

Edge edges[5] = {
    {0, 1, 10},
    {0, 2, 6},
    {0, 3, 5},
    {1, 3, 15},
    {2, 3, 4}
};

// Create parent and rank arrays and initialize them
// Your code here

Hint

Use a for loop from 0 to 3 to set parent[i] = i and rank[i] = 0.

3

Implement Kruskal's algorithm core logic

Write functions findParent(int node) to find the root parent with path compression, and unionSet(int u, int v) to union two sets by rank. Then write a function kruskal() that sorts edges by weight, iterates over them, and adds edges to MST if their parents differ. Store MST edges in an array result and keep track of e (count of MST edges).

DSA C

typedef struct {
    int src;
    int dest;
    int weight;
} Edge;

Edge edges[5] = {
    {0, 1, 10},
    {0, 2, 6},
    {0, 3, 5},
    {1, 3, 15},
    {2, 3, 4}
};

int parent[4];
int rank[4];

void makeSet() {
    for (int i = 0; i < 4; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

// Write findParent, unionSet, and kruskal functions
// Your code here

Hint

Use qsort to sort edges by weight. Use findParent and unionSet to check and join sets. Add edges to result if they connect different sets.

4

Run Kruskal and print MST

In main(), call makeSet() and then kruskal() to print the MST edges and total cost.

DSA C

typedef struct {
    int src;
    int dest;
    int weight;
} Edge;

Edge edges[5] = {
    {0, 1, 10},
    {0, 2, 6},
    {0, 3, 5},
    {1, 3, 15},
    {2, 3, 4}
};

int parent[4];
int rank[4];

void makeSet() {
    for (int i = 0; i weight - edgeB->weight;
}

void kruskal() {
    Edge result[4];
    int e = 0;
    int i = 0;

    qsort(edges, 5, sizeof(Edge), compareEdges);

    while (e < 3 && i < 5) {
        Edge nextEdge = edges[i++];
        int u = findParent(nextEdge.src);
        int v = findParent(nextEdge.dest);

        if (u != v) {
            result[e++] = nextEdge;
            unionSet(u, v);
        }
    }

    printf("Edges in MST:\n");
    int totalWeight = 0;
    for (int j = 0; j < e; j++) {
        printf("%d - %d : %d\n", result[j].src, result[j].dest, result[j].weight);
        totalWeight += result[j].weight;
    }
    printf("Total cost: %d\n", totalWeight);
}

// Write main function to call makeSet and kruskal
// Your code here

Hint

Call makeSet() first to initialize sets, then call kruskal() to print the MST edges and total cost.

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