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 that uses Kruskal's algorithm to find the minimum spanning tree (MST) of a given weighted graph. The MST connects all nodes with the smallest total edge cost.

📋 What You'll Learn

Create a list of edges with exact weights and nodes

Create a parent array for union-find with exact initialization

Implement the union-find functions findParent and unionSets

Sort edges by weight using std::sort

Build MST by adding edges without creating cycles

Print the MST edges and total cost exactly as specified

💡 Why This Matters

🌍 Real World

Network design, circuit design, and clustering problems often require connecting points with minimum total cost without loops.

💼 Career

Understanding MST algorithms like Kruskal's is essential for software engineers working on network optimization, infrastructure planning, and graph-based problem solving.

1

Create the graph edges

Create a vector of tuples called edges with these exact entries: {0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}. Each tuple represents an edge with (node1, node2, weight).

DSA C++

#include 
#include 
#include 
#include 

int main() {
    // Create vector of edges with given tuples
    // Your code here
    return 0;
}

Hint

Use std::vector and std::tuple to store edges as (node1, node2, weight).

2

Initialize the parent array for union-find

Create a vector of integers called parent with size 4. Initialize it so that each element is its own index: parent = {0, 1, 2, 3}.

DSA C++

#include 
#include 
#include 
#include 

int main() {
    std::vector> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };
    // Create parent vector with values 0,1,2,3
    // Your code here
    return 0;
}

Hint

Use std::vector parent = {0, 1, 2, 3}; to initialize.

3

Implement union-find and build MST

Write the functions findParent and unionSets to manage the parent array. Then sort edges by weight using std::sort. Use a for loop with variables u, v, w to iterate over edges. For each edge, if findParent(u) != findParent(v), call unionSets(u, v) and add the edge to a vector called mst. Also keep track of the total cost in an integer variable totalCost.

DSA C++

#include 
#include 
#include 
#include 

int findParent(int node, std::vector& parent) {
    // Implement findParent with path compression
    // Your code here
}

void unionSets(int u, int v, std::vector& parent) {
    // Implement unionSets to join sets
    // Your code here
}

int main() {
    std::vector> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };
    std::vector parent = {0, 1, 2, 3};
    // Sort edges by weight
    // Create mst vector and totalCost variable
    // Loop over edges and build MST
    // Your code here
    return 0;
}

Hint

Use recursion with path compression in findParent. Use std::sort with a lambda to sort edges by weight. Loop over edges and use union-find to avoid cycles.

4

Print the MST edges and total cost

Use a for loop with variables u, v, w to iterate over mst. Print each edge in the format: "Edge: u - v with weight w". After the loop, print the total cost in the format: "Total cost of MST: totalCost".

DSA C++

#include 
#include 
#include 
#include 

int findParent(int node, std::vector& parent) {
    if (parent[node] == node) {
        return node;
    }
    parent[node] = findParent(parent[node], parent);
    return parent[node];
}

void unionSets(int u, int v, std::vector& parent) {
    int pu = findParent(u, parent);
    int pv = findParent(v, parent);
    if (pu != pv) {
        parent[pu] = pv;
    }
}

int main() {
    std::vector> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };
    std::vector parent = {0, 1, 2, 3};

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

    std::vector> mst;
    int totalCost = 0;

    for (auto &[u, v, w] : edges) {
        if (findParent(u, parent) != findParent(v, parent)) {
            unionSets(u, v, parent);
            mst.push_back({u, v, w});
            totalCost += w;
        }
    }
    // Print MST edges and total cost
    // Your code here
    return 0;
}

Hint

Use a for loop to print each edge in mst. Then print the total cost.

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