Minimum Spanning Tree Kruskal's Algorithm in DSA C++ - Execution Trace

Concept Flow - Minimum Spanning Tree Kruskal's Algorithm

Start with all edges sorted by weight

↓

Pick smallest edge

↓

Check if adding edge forms cycle?

↓

Add edge to MST

↓

All vertices connected?

↓

Done

↓

Repeat

Kruskal's algorithm sorts edges by weight, then adds edges one by one if they don't form a cycle, until all vertices are connected.

Execution Sample

DSA C++

edges = [(1,2,1), (2,3,2), (1,3,3)]
sort edges by weight
for edge in edges:
  if no cycle:
    add edge to MST

This code sorts edges by weight and adds them to the MST if they don't create a cycle.

Execution Table

Step	Operation	Edge Considered	Cycle Check Result	MST Edges	Visual State
1	Sort edges	N/A	N/A	[]	MST: []
2	Consider edge	(1,2,1)	No cycle	[(1,2)]	1--2
3	Consider edge	(2,3,2)	No cycle	[(1,2), (2,3)]	1--2--3
4	Consider edge	(1,3,3)	Cycle detected	[(1,2), (2,3)]	1--2--3 (edge 1-3 skipped)
5	Check completion	N/A	All vertices connected	[(1,2), (2,3)]	Final MST: 1--2--3

💡 All vertices connected, MST complete with edges (1,2) and (2,3)

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
edges_sorted	[(1,2,1), (2,3,2), (1,3,3)]	[(1,2,1), (2,3,2), (1,3,3)]	[(1,2,1), (2,3,2), (1,3,3)]	[(1,2,1), (2,3,2), (1,3,3)]	[(1,2,1), (2,3,2), (1,3,3)]
MST_edges	[]	[(1,2)]	[(1,2), (2,3)]	[(1,2), (2,3)]	[(1,2), (2,3)]
connected_components	3 (each vertex separate)	2 (1 and 2 connected)	1 (all connected)	1 (all connected)	1 (all connected)

Key Moments - 3 Insights

Why do we check for cycles before adding an edge?

Adding an edge that forms a cycle would break the tree property of MST. The execution_table rows 3 and 4 show that edge (1,3) is skipped because it creates a cycle.

How do we know when the MST is complete?

When all vertices are connected in one component, the MST is complete. The variable_tracker shows connected_components reduce from 3 to 1 by step 3, and execution_table step 5 confirms completion.

Why do we sort edges by weight first?

Sorting ensures we always pick the smallest edge available to keep MST weight minimal. Execution_table step 1 shows edges sorted before processing.

Visual Quiz - 3 Questions

Look at the execution_table, what is the MST after step 3?

A [(1,2), (2,3)]

B [(1,3)]

C [(2,3), (1,3)]

D []

💡 Hint

Check the MST Edges column at step 3 in the execution_table.

At which step does the algorithm detect a cycle?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the Cycle Check Result column in the execution_table.

If the edge (1,3,3) had weight 0.5, what would happen in the execution_table?

A It would still be skipped due to cycle

B It would be added first to MST

C It would be added last

D Algorithm would fail

💡 Hint

Edges are sorted by weight first; lower weight edges are considered earlier.

Concept Snapshot

Kruskal's Algorithm:
- Sort all edges by weight
- Pick smallest edge
- Add if no cycle formed
- Repeat until all vertices connected
- Uses Union-Find or similar for cycle check

Full Transcript

Kruskal's algorithm builds a minimum spanning tree by sorting edges by weight and adding them one by one if they do not create a cycle. The process continues until all vertices are connected. Cycle detection prevents loops, ensuring the result is a tree. The example shows edges (1,2) and (2,3) added, while (1,3) is skipped due to cycle. The algorithm stops when all vertices form a single connected component.

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