Minimum Spanning Tree Kruskal's Algorithm in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the edge list vector.

DSA C++

std::vector<std::pair<int, std::pair<int, int>>> [1];

Drag options to blanks, or click blank then click option'

Aedges

Bgraph

Cnodes

Dweights

Attempts:

3 left

💡 Hint

Common Mistakes

Using a variable name that does not represent edges.

Using a name that implies nodes or weights only.

The vector named edges stores all edges as pairs of weight and node pairs.

2fill in blank

medium

Complete the code to sort edges by their weight.

DSA C++

std::sort([1].begin(), [1].end());

Drag options to blanks, or click blank then click option'

Aweights

Bgraph

Cnodes

Dedges

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting the wrong vector like nodes or weights.

Not sorting at all.

We sort the edges vector to process edges from smallest to largest weight.

3fill in blank

hard

Fix the error in the union-find find function to correctly find the parent.

DSA C++

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

Drag options to blanks, or click blank then click option'

A-1

Bnode

C0

Dparent[node]

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if parent[node] equals node or 0 instead of -1.

Returning wrong values causing infinite recursion.

The root parent is identified by parent[node] == -1 meaning no parent above.

4fill in blank

hard

Fill both blanks to correctly union two sets by their parents.

DSA C++

void unionSets(int u, int v, std::vector<int>& parent) {
    int parentU = findParent(u, parent);
    int parentV = findParent(v, parent);
    if (parentU != parentV) {
        parent[[1]] = [2];
    }
}

Drag options to blanks, or click blank then click option'

AparentU

BparentV

Cu

Dv

Attempts:

3 left

💡 Hint

Common Mistakes

Using node variables instead of their parents.

Assigning in the wrong direction causing cycles.

We set the parent of parentU to parentV to merge the sets.

5fill in blank

hard

Fill all three blanks to add edges to MST and union their sets.

DSA C++

for (auto& edge : edges) {
    int weight = edge.first;
    int u = edge.second.first;
    int v = edge.second.second;
    if (findParent(u, parent) != findParent(v, parent)) {
        mst.push_back([1]);
        unionSets([2], [3], parent);
    }
}

Drag options to blanks, or click blank then click option'

Aedge

Bu

Cv

Dweight

Attempts:

3 left

💡 Hint

Common Mistakes

Adding only weight or nodes instead of the full edge.

Unioning wrong nodes or using weight instead of nodes.

We add the whole edge to MST and union the sets of u and v.

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