Minimum Spanning Tree Kruskal's Algorithm in DSA Rust - 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

↓

Repeat until MST has (V-1) edges

↓

Done

Kruskal's algorithm sorts edges by weight, then adds the smallest edge that doesn't create a cycle, repeating until the MST is complete.

Execution Sample

DSA Rust

let mut edges: Vec<(usize, usize, usize)> = vec![(1,2,1), (1,3,3), (2,3,2), (2,4,4), (3,4,5)];
edges.sort_by_key(|e| e.2);
let mut mst: Vec<(usize, usize, usize)> = Vec::new();
for edge in edges {
  let (u, v, w) = edge;
  if !forms_cycle(u, v) {
    mst.push((u, v, w));
  }
}

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

Execution Table

Step	Operation	Edge Considered	Cycle Check Result	MST Edges	Visual State
1	Sort edges by weight	-	-	[]	Edges sorted: (1-2:1), (2-3:2), (1-3:3), (2-4:4), (3-4:5)
2	Consider edge	(1-2:1)	No cycle	[(1-2:1)]	MST: 1--1--2
3	Consider edge	(2-3:2)	No cycle	[(1-2:1), (2-3:2)]	MST: 1--1--2--2--3
4	Consider edge	(1-3:3)	Cycle detected	[(1-2:1), (2-3:2)]	MST unchanged
5	Consider edge	(2-4:4)	No cycle	[(1-2:1), (2-3:2), (2-4:4)]	MST: 1--1--2--2--3 and 2--4--4
6	Consider edge	(3-4:5)	Cycle detected	[(1-2:1), (2-3:2), (2-4:4)]	MST unchanged
7	Stop	-	-	[(1-2:1), (2-3:2), (2-4:4)]	MST complete with 3 edges

💡 MST has (V-1) = 3 edges, so algorithm stops

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
MST Edges	[]	[(1-2:1)]	[(1-2:1), (2-3:2)]	[(1-2:1), (2-3:2)]	[(1-2:1), (2-3:2), (2-4:4)]	[(1-2:1), (2-3:2), (2-4:4)]	[(1-2:1), (2-3:2), (2-4:4)]
Edges Considered	[(1-2:1), (2-3:2), (1-3:3), (2-4:4), (3-4:5)]	[(2-3:2), (1-3:3), (2-4:4), (3-4:5)]	[(1-3:3), (2-4:4), (3-4:5)]	[(2-4:4), (3-4:5)]	[(3-4:5)]	[]	[]
Disjoint Set Parents	[1->1,2->2,3->3,4->4]	[1->1,2->1,3->3,4->4]	[1->1,2->1,3->1,4->4]	[1->1,2->1,3->1,4->4]	[1->1,2->1,3->1,4->1]	[1->1,2->1,3->1,4->1]	[1->1,2->1,3->1,4->1]

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. The execution_table rows 3 and 4 show edges rejected because they create cycles.

How do we know when to stop adding edges?

We stop when MST has (V-1) edges. Here, after step 6, MST has 3 edges for 4 vertices, so the algorithm stops (see exit_note).

What is the role of the disjoint set parents in cycle detection?

Disjoint set parents track connected components. If two vertices share the same parent, adding an edge between them forms a cycle. This is shown in variable_tracker for 'Disjoint Set Parents'.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what happens when considering edge (1-3:3)?

A Edge is added to MST

B Edge weight is updated

C Edge is discarded due to cycle

D Algorithm stops

💡 Hint

Check 'Cycle Check Result' and 'MST Edges' columns at step 4 in execution_table

At which step does the MST reach the required number of edges to stop?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look at 'MST Edges' count and exit_note in execution_table

If the edge (2-4:4) was considered before (2-3:2), how would the MST edges change after step 3?

A MST would have edges (1-2:1) and (2-4:4)

B MST would have edges (1-2:1) and (1-3:3)

C MST would have edges (1-2:1) and (2-3:2)

D MST would be empty

💡 Hint

Check the order of edges and how cycle checks affect MST Edges in variable_tracker

Concept Snapshot

Kruskal's Algorithm for MST:
- Sort all edges by weight
- Pick smallest edge that doesn't form a cycle
- Use disjoint sets to detect cycles
- Stop when MST has (V-1) edges
- Result is a minimum spanning tree connecting all vertices

Full Transcript

Kruskal's algorithm builds a minimum spanning tree by sorting edges by weight and adding them one by one if they don't create a cycle. It uses a disjoint set data structure to check if two vertices belong to the same connected component. If they do, adding the edge would form a cycle, so it is skipped. The process continues until the MST contains exactly one less edge than the number of vertices. This ensures the MST connects all vertices with minimum total edge weight.

Practice

1. What is the main goal of Kruskal's Algorithm in graph theory?

easy

A. To sort the vertices of a graph

B. To find the minimum spanning tree of a graph

C. To detect cycles in a graph

D. To find the shortest path between two nodes

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 algorithms or cycle detection, Kruskal's specifically builds a minimum spanning tree.

3. Final Answer:

   To find the minimum spanning tree of a graph -> Option B

4. Quick Check:

   Minimum Spanning Tree = Kruskal's Algorithm goal [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 Rust data structure is most suitable to efficiently implement the union-find (disjoint set) used in Kruskal's Algorithm?

easy

A. Vec<(usize, usize)>

B. HashMap

C. Vec<usize>

D. LinkedList<usize>

Solution

1. Step 1: Identify union-find structure needs

   Union-find requires quick parent lookup and union operations, best done with an array-like structure where index is node and value is parent.

2. Step 2: Match Rust data structures

   Vec<usize> is a simple array of parents, perfect for union-find. HashMap is slower, LinkedList is inefficient, Vec of tuples is not direct parent mapping.

3. Final Answer:

   Vec<usize> -> Option C

4. Quick Check:

   Union-find uses parent array = Vec<usize> [OK]

Hint: Use Vec for parent array in union-find [OK]

Common Mistakes:

• Using HashMap instead of Vec for parent tracking
• Choosing LinkedList which is slow for indexing
• Using Vec of tuples which is unnecessary

3. What will be the output edges of the MST after running Kruskal's Algorithm on this graph? Edges with weights:

(0, 1, 4)
(0, 2, 3)
(1, 2, 1)
(1, 3, 2)
(2, 3, 4)
(3, 4, 2)
(4, 5, 6)

Assume vertices are 0 to 5.

medium

A. [(1, 2, 1), (1, 3, 2), (3, 4, 2), (0, 2, 3), (4, 5, 6)]

B. [(1, 2, 1), (1, 3, 2), (3, 4, 2), (0, 1, 4), (4, 5, 6)]

C. [(0, 2, 3), (1, 3, 2), (3, 4, 2), (4, 5, 6), (0, 1, 4)]

D. [(1, 2, 1), (0, 2, 3), (3, 4, 2), (4, 5, 6), (0, 1, 4)]

Solution

1. Step 1: Sort edges by weight

   Sorted edges: (1,2,1), (1,3,2), (3,4,2), (0,2,3), (0,1,4), (2,3,4), (4,5,6)

2. Step 2: Pick edges without cycles

   Pick (1,2,1), (1,3,2), (3,4,2), (0,2,3) connects 0,1,2,3,4 without cycle. Then (4,5,6) connects 5. Skip (0,1,4) and (2,3,4) as they form cycles.

3. Final Answer:

   [(1, 2, 1), (1, 3, 2), (3, 4, 2), (0, 2, 3), (4, 5, 6)] -> Option A

4. Quick Check:

   Edges chosen by increasing weight without cycles = [(1, 2, 1), (1, 3, 2), (3, 4, 2), (0, 2, 3), (4, 5, 6)] [OK]

Hint: Sort edges by weight, pick smallest without cycle [OK]

Common Mistakes:

• Including edges that form cycles
• Not sorting edges by weight
• Skipping necessary edges to connect all nodes

4. Identify the bug in this Rust snippet implementing Kruskal's union-find 'find' function:

fn find(parent: &mut Vec<usize>, x: usize) -> usize {
    if parent[x] != x {
        parent[x] = find(parent, parent[x]);
    }
    x
}

medium

A. Missing return of updated parent[x] after recursion

B. Should not use mutable reference for parent

C. Incorrect base condition for recursion

D. Function should return bool instead of usize

Solution

1. Step 1: Analyze the recursive find function

   The function updates parent[x] recursively but always returns x, ignoring updated parent[x].

2. Step 2: Correct return statement

   It should return parent[x] after recursion to propagate the root parent upwards.

3. Final Answer:

   Missing return of updated parent[x] after recursion -> Option A

4. Quick Check:

   Return updated parent[x] in find function [OK]

Hint: Return recursive find result, not original x [OK]

Common Mistakes:

• Returning x instead of parent[x]
• Not using mutable reference for path compression
• Changing return type incorrectly

5. Given a graph with edges:

(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)

If you run Kruskal's Algorithm but mistakenly sort edges in descending order by weight, what will be the total weight of the resulting spanning tree?

hard

A. 29

B. 25

C. Incorrect MST formed, total weight undefined

D. 31

Solution

1. Step 1: Sort edges descending by weight

   Edges sorted descending: (1,3,15), (0,1,10), (0,2,6), (0,3,5), (2,3,4)

2. Step 2: Pick edges without cycles in this order

   Pick (1,3,15), then (0,1,10) connects 0,1,3. Next (0,2,6) connects 2. Total edges: 3 edges connecting all 4 nodes.

3. Step 3: Calculate total weight

   Sum = 15 + 10 + 6 = 31. But (0,3,5) and (2,3,4) are skipped to avoid cycles.

4. Step 4: Check if cycle avoided correctly

   Actually, (0,3,5) connects 0 and 3 which are already connected, so skipped. (2,3,4) connects 2 and 3, but 2 is connected to 0, and 3 is connected to 1, so adding (2,3,4) creates cycle, skipped.

5. Final Answer:

   31 -> Option D

6. Quick Check:

   Descending sort picks heavy edges first, total weight = 31 [OK]

Hint: Descending sort picks heavy edges, MST weight increases [OK]

Common Mistakes:

• Assuming MST weight stays minimal with descending sort
• Adding edges that create cycles
• Confusing total weight calculation