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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kruskal's MST edges

What is the output of the edges included in the MST after running Kruskal's algorithm on the given graph?

DSA Rust

use std::collections::HashMap;

#[derive(Debug, Clone)]
struct Edge {
    u: usize,
    v: usize,
    weight: i32,
}

struct DisjointSet {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl DisjointSet {
    fn new(n: usize) -> Self {
        DisjointSet {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

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

    fn union(&mut self, x: usize, y: usize) -> bool {
        let xroot = self.find(x);
        let yroot = self.find(y);
        if xroot == yroot {
            return false;
        }
        if self.rank[xroot] < self.rank[yroot] {
            self.parent[xroot] = yroot;
        } else if self.rank[xroot] > self.rank[yroot] {
            self.parent[yroot] = xroot;
        } else {
            self.parent[yroot] = xroot;
            self.rank[xroot] += 1;
        }
        true
    }
}

fn kruskal(n: usize, edges: &mut Vec<Edge>) -> Vec<Edge> {
    edges.sort_by_key(|e| e.weight);
    let mut ds = DisjointSet::new(n);
    let mut mst = Vec::new();
    for edge in edges.iter() {
        if ds.union(edge.u, edge.v) {
            mst.push(edge.clone());
        }
    }
    mst
}

fn main() {
    let mut edges = vec![
        Edge { u: 0, v: 1, weight: 10 },
        Edge { u: 0, v: 2, weight: 6 },
        Edge { u: 0, v: 3, weight: 5 },
        Edge { u: 1, v: 3, weight: 15 },
        Edge { u: 2, v: 3, weight: 4 },
    ];
    let mst = kruskal(4, &mut edges);
    for e in mst {
        println!("{} - {} : {}", e.u, e.v, e.weight);
    }
}

A

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

B

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

C

0 - 2 : 6
1 - 3 : 15
0 - 3 : 5

D

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

💡 Hint

Sort edges by weight and pick edges that don't form a cycle.

Kruskal's algorithm sorts edges by weight and adds edges to MST if they connect different sets.

Edges chosen are (2-3:4), (0-3:5), and (0-1:10).

🧠 Conceptual

intermediate

Number of edges in MST for a graph with 7 vertices

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

A 7

B 6

C 5

D 8

💡 Hint

MST connects all vertices with minimum edges to avoid cycles.

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

🔧 Debug

advanced

Identify the bug in this Kruskal's union function

What error will this union function cause when used in Kruskal's algorithm?

DSA Rust

fn union(&mut self, x: usize, y: usize) -> bool {
    let xroot = self.find(x);
    let yroot = self.find(y);
    if xroot == yroot {
        return false;
    }
    if self.rank[xroot] > self.rank[yroot] {
        self.parent[yroot] = xroot;
    } else {
        self.parent[xroot] = yroot;
        if self.rank[xroot] == self.rank[yroot] {
            self.rank[yroot] += 1;
        }
    }
    true
}

A The rank update is done on the wrong root causing incorrect tree height tracking.

B It causes a stack overflow due to infinite recursion in find.

C It will always return false, so no edges get added to MST.

D It causes a compilation error due to missing lifetime annotations.

💡 Hint

Check which root's rank is incremented after union.

The rank should be incremented on the root that becomes the parent.

Here, rank is incremented on yroot even if xroot becomes parent, causing wrong rank info.

❓ Predict Output

advanced

Output of MST total weight calculation

What is the total weight of the MST computed by this code snippet?

DSA Rust

let mut edges = vec![
    Edge { u: 0, v: 1, weight: 7 },
    Edge { u: 0, v: 3, weight: 5 },
    Edge { u: 1, v: 2, weight: 8 },
    Edge { u: 1, v: 3, weight: 9 },
    Edge { u: 1, v: 4, weight: 7 },
    Edge { u: 2, v: 4, weight: 5 },
    Edge { u: 3, v: 4, weight: 15 },
    Edge { u: 3, v: 5, weight: 6 },
    Edge { u: 4, v: 5, weight: 8 },
    Edge { u: 4, v: 6, weight: 9 },
    Edge { u: 5, v: 6, weight: 11 },
];
let mst = kruskal(7, &mut edges);
let total_weight: i32 = mst.iter().map(|e| e.weight).sum();
println!("{}", total_weight);

A 41

B 44

C 37

D 39

💡 Hint

Sum weights of edges chosen by Kruskal's algorithm.

The MST edges chosen have weights: 5, 5, 6, 7, 7, 7 (total 37).

🧠 Conceptual

expert

Why does Kruskal's algorithm use a Disjoint Set data structure?

What is the main reason Kruskal's algorithm uses a Disjoint Set (Union-Find) data structure?

A To keep track of the degree of each vertex during MST construction.

B To store the graph edges in sorted order by weight.

C To find the shortest path between two vertices in the graph.

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

💡 Hint

Think about cycle detection in MST building.

Disjoint Set helps quickly determine if two vertices are already connected, preventing cycles.

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