Why Minimum Spanning Tree Kruskal's Algorithm in DSA C++?

The Big Idea

Discover how to connect everything with the least cost without getting lost in endless choices!

The Scenario

Imagine you have a map of cities connected by roads, and you want to build a network that connects all cities with the least total road length.

Trying to pick roads one by one by guessing which is shortest and still connects all cities can be very confusing and slow.

The Problem

Manually checking every possible combination of roads to find the shortest total length is very slow and easy to make mistakes.

You might accidentally create loops or miss some cities, making the network incomplete or inefficient.

The Solution

Kruskal's Algorithm helps by sorting all roads by length and then adding the shortest roads one by one, only if they connect new cities without creating loops.

This way, it quickly builds the best network connecting all cities with minimum total road length.

Before vs After

✗ Before

vector<Edge> roads; // manually pick roads
// check all combinations for shortest total
// avoid loops manually
// very complex and slow

✓ After

sort(roads.begin(), roads.end(), compareByLength);
for (Edge road : roads) {
  if (connectsNewCities(road)) {
    addRoad(road);
  }
}

What It Enables

This algorithm makes it easy to build the cheapest network connecting all points without loops, saving time and money.

Real Life Example

Building electrical grids or internet cables connecting multiple cities with the least cost and no redundant connections.

Key Takeaways

Manual road selection is slow and error-prone.

Kruskal's Algorithm sorts roads and adds shortest safe roads step-by-step.

It guarantees the cheapest network connecting all points without loops.

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