Minimum Spanning Tree Kruskal's Algorithm in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kruskal's MST edges

What is the output of the following C++ code that uses Kruskal's algorithm to find the MST edges?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int parent[5];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a;
}

int main() {
    int n = 4;
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };
    for (int i = 0; i < n; i++) parent[i] = i;
    sort(edges.begin(), edges.end());
    vector<Edge> mst;
    for (auto& e : edges) {
        if (find(e.u) != find(e.v)) {
            unite(e.u, e.v);
            mst.push_back(e);
        }
    }
    for (auto& e : mst) {
        cout << e.u << "-" << e.v << " " << e.w << "\n";
    }
    return 0;
}

A

0-2 6
2-3 4
0-1 10

B

0-3 5
2-3 4
1-3 15

C

0-1 10
0-2 6
1-3 15

D

2-3 4
0-3 5
0-1 10

💡 Hint

Remember Kruskal's algorithm picks edges in increasing order of weight and avoids cycles.

The edges sorted by weight are (2-3:4), (0-3:5), (0-2:6), (0-1:10), (1-3:15). The MST includes edges 2-3, 0-3, and 0-1 without forming cycles.

🧠 Conceptual

intermediate

Number of edges in MST for a connected graph

For a connected graph with 7 vertices, how many edges will the Minimum Spanning Tree (MST) contain?

A 6

B 7

C 5

D 8

💡 Hint

Think about how many edges connect all vertices without cycles.

An MST for a connected graph with n vertices always has exactly n-1 edges.

🔧 Debug

advanced

Identify the error in this Kruskal's implementation snippet

What error will the following code snippet cause when running Kruskal's algorithm?

DSA C++

int find(int x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[a] = b;
}

A The union operation may create cycles because it does not attach smaller tree to larger.

B The find function does not perform path compression, causing slower queries but no error.

C The union operation incorrectly assigns parent[a] = b causing incorrect MST.

D No error; code runs correctly and finds MST.

💡 Hint

Check how union assigns parents and how it affects the tree structure.

In union, assigning parent[a] = b is incorrect if b is not root; it should assign parent[b] = a or use union by rank. This can cause incorrect MST.

❓ Predict Output

advanced

Output of MST total weight calculation

What is the output of the following code that calculates the total weight of MST using Kruskal's algorithm?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int parent[6];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a;
}

int main() {
    int n = 5;
    vector<Edge> edges = {
        {0, 1, 2},
        {0, 3, 6},
        {1, 2, 3},
        {1, 3, 8},
        {1, 4, 5},
        {2, 4, 7}
    };
    for (int i = 0; i < n; i++) parent[i] = i;
    sort(edges.begin(), edges.end());
    int total_weight = 0;
    for (auto& e : edges) {
        if (find(e.u) != find(e.v)) {
            unite(e.u, e.v);
            total_weight += e.w;
        }
    }
    cout << total_weight << "\n";
    return 0;
}

A 14

B 16

C 18

D 20

💡 Hint

Sum weights of edges chosen by Kruskal's algorithm in ascending order without cycles.

Edges chosen: (0-1:2), (1-2:3), (1-4:5), (0-3:6). Total = 2+3+5+6=16 is correct because edges sorted: 2,3,5,6,7,8. MST picks 2,3,5,6 total 16.

🧠 Conceptual

expert

Why does Kruskal's algorithm use Union-Find?

Why is the Union-Find data structure essential in Kruskal's algorithm?

A To efficiently check if adding an edge creates a cycle by checking if two vertices belong to the same set.

B To find the shortest path between two vertices.

C To store the final MST edges in order.

D To sort edges by weight before processing them.

💡 Hint

Think about how Kruskal avoids cycles while adding edges.

Union-Find helps quickly determine if two vertices are already connected (in the same set), preventing cycles when adding edges.

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