Minimum Spanning Tree Kruskal's Algorithm in DSA Rust

Mental Model

Pick the smallest edges one by one without making loops until all points connect.

Analogy: Imagine connecting cities with roads. You want to build the cheapest roads so every city is reachable without any circle of roads.

Graph:
  A---2---B
  |       |
  3       1
  |       |
  C---4---D

Edges with weights: 1, 2, 3, 4
Goal: connect all cities with smallest total road cost.

Dry Run Walkthrough

Input: Graph with edges: (A-B:2), (B-D:1), (A-C:3), (C-D:4)

Goal: Find the set of edges connecting all nodes with minimum total weight and no cycles.

Step 1: Sort edges by weight: (B-D:1), (A-B:2), (A-C:3), (C-D:4)

Edges sorted: 1(B-D), 2(A-B), 3(A-C), 4(C-D)

Why: We pick edges from smallest to largest to keep total cost low.

Step 2: Pick edge (B-D:1), add to MST

MST edges: B-D(1)
Sets: {A}, {B,D}, {C}

Why: No cycle formed, connect B and D.

Step 3: Pick edge (A-B:2), add to MST

MST edges: B-D(1), A-B(2)
Sets: {A,B,D}, {C}

Why: Connect A to B-D group without cycle.

Step 4: Pick edge (A-C:3), add to MST

MST edges: B-D(1), A-B(2), A-C(3)
Sets: {A,B,C,D}

Why: Connect C to the group, all nodes connected now.

Step 5: Skip edge (C-D:4) because it forms a cycle

MST edges unchanged: B-D(1), A-B(2), A-C(3)

Why: Adding this edge would create a loop, so we skip it.

Result:

MST edges: B-D(1) -> A-B(2) -> A-C(3)
Total weight: 6

Annotated Code

DSA Rust

use std::collections::HashMap;

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

struct DisjointSet {
    parent: HashMap<char, char>,
    rank: HashMap<char, i32>,
}

impl DisjointSet {
    fn new(nodes: &[char]) -> Self {
        let mut parent = HashMap::new();
        let mut rank = HashMap::new();
        for &node in nodes {
            parent.insert(node, node);
            rank.insert(node, 0);
        }
        DisjointSet { parent, rank }
    }

    fn find(&mut self, x: char) -> char {
        if self.parent[&x] != x {
            let p = self.parent[&x];
            let root = self.find(p);
            self.parent.insert(x, root); // path compression
        }
        self.parent[&x]
    }

    fn union(&mut self, x: char, y: char) -> bool {
        let xroot = self.find(x);
        let yroot = self.find(y);
        if xroot == yroot {
            return false; // already connected
        }
        let xrank = self.rank[&xroot];
        let yrank = self.rank[&yroot];
        if xrank < yrank {
            self.parent.insert(xroot, yroot);
        } else if xrank > yrank {
            self.parent.insert(yroot, xroot);
        } else {
            self.parent.insert(yroot, xroot);
            *self.rank.get_mut(&xroot).unwrap() += 1;
        }
        true
    }
}

fn kruskal(nodes: &[char], edges: &mut Vec<Edge>) -> Vec<Edge> {
    edges.sort_by_key(|e| e.weight); // sort edges by weight
    let mut ds = DisjointSet::new(nodes);
    let mut mst = Vec::new();
    for edge in edges.iter() {
        if ds.union(edge.u, edge.v) {
            mst.push(Edge { u: edge.u, v: edge.v, weight: edge.weight });
        }
    }
    mst
}

fn main() {
    let nodes = vec!['A', 'B', 'C', 'D'];
    let mut edges = vec![
        Edge { u: 'A', v: 'B', weight: 2 },
        Edge { u: 'B', v: 'D', weight: 1 },
        Edge { u: 'A', v: 'C', weight: 3 },
        Edge { u: 'C', v: 'D', weight: 4 },
    ];
    let mst = kruskal(&nodes, &mut edges);
    let total_weight: i32 = mst.iter().map(|e| e.weight).sum();
    for edge in &mst {
        println!("{} - {} : {}", edge.u, edge.v, edge.weight);
    }
    println!("Total weight: {}", total_weight);
}

edges.sort_by_key(|e| e.weight);

sort edges by weight ascending to pick smallest first

if ds.union(edge.u, edge.v) {

try to connect nodes if they are not already connected to avoid cycles

self.parent.insert(xroot, yroot);

attach one tree root to another to merge sets

self.parent.insert(yroot, xroot);

attach one tree root to another to merge sets

*self.rank.get_mut(&xroot).unwrap() += 1;

increase rank when two trees of same height merge

Output

B - D : 1

A - B : 2

A - C : 3

Total weight: 6

Complexity Analysis

Time: O(E log E) because sorting edges dominates and union-find operations are almost O(1)

Space: O(V) for storing parent and rank of each node in disjoint set

vs Alternative: Compared to Prim's algorithm, Kruskal is simpler for sparse graphs and uses sorting edges instead of priority queues.

Edge Cases

Empty graph (no nodes)

Returns empty MST without error

DSA Rust

for &node in nodes { parent.insert(node, node); }

Graph with one node and no edges

MST is empty as no edges to connect

DSA Rust

for &node in nodes { parent.insert(node, node); }

Graph with multiple edges having same weight

Algorithm picks edges in sorted order, ties broken by stable sort

DSA Rust

edges.sort_by_key(|e| e.weight);

When to Use This Pattern

When you need to connect all points with minimum total cost and avoid cycles, use Kruskal's algorithm because it picks edges by weight and uses union-find to detect cycles.

Common Mistakes

Mistake: Not using union-find to detect cycles, causing loops in MST
Fix: Implement union-find data structure to check if adding an edge creates a cycle

Mistake: Not sorting edges by weight before processing
Fix: Sort edges ascending by weight before starting to pick edges

Summary

Builds a minimum cost set of edges connecting all nodes without cycles.

Use when you have a weighted graph and want the cheapest way to connect all points.

Pick edges from smallest to largest and skip those that form cycles using union-find.

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