Minimum Spanning Tree Kruskal's Algorithm in DSA Rust - Build from Scratch

Minimum Spanning Tree using Kruskal's Algorithm

📖 Scenario: You are working as a network engineer. You need to connect several computers with cables. Each cable has a cost. Your goal is to connect all computers with the least total cost without any loops.

🎯 Goal: Build a program that uses Kruskal's algorithm to find the minimum spanning tree (MST) of a graph. The MST connects all nodes with the smallest total edge cost.

📋 What You'll Learn

Create a list of edges with exact nodes and weights

Create a union-find data structure to help detect cycles

Implement Kruskal's algorithm to select edges for MST

Print the edges in the MST and their total cost

💡 Why This Matters

🌍 Real World

Network engineers use MST algorithms to design cost-efficient networks connecting computers or devices.

💼 Career

Understanding MST and union-find is important for roles in network design, optimization, and algorithm development.

1

Create the list of edges

Create a vector called edges containing these exact tuples representing edges: (0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4), (3, 4, 2), (4, 5, 6).

DSA Rust

# Create a vector called edges with the given tuples
# Your code here

Hint

Use let edges = vec![(0, 1, 4), ...]; to create the list of edges.

2

Create the union-find structure

Create a struct called UnionFind with a vector parent to track each node's parent. Add an impl block with a new function that takes size: usize and returns a UnionFind where each node is its own parent.

DSA Rust

fn main() {
    let edges = vec![
        (0, 1, 4),
        (0, 2, 3),
        (1, 2, 1),
        (1, 3, 2),
        (2, 3, 4),
        (3, 4, 2),
        (4, 5, 6),
    ];
}

// Create UnionFind struct and new function
// Your code here

Hint

Define struct UnionFind { parent: Vec } and implement new to initialize parents.

3

Implement Kruskal's algorithm core logic

Add find and union methods to UnionFind. Then, in main, sort edges by weight, create a UnionFind for 6 nodes, and iterate over edges. For each edge, if the nodes are in different sets, union them and add the edge to a vector mst.

DSA Rust

struct UnionFind {
    parent: Vec,
}

impl UnionFind {
    fn new(size: usize) -> Self {
        let mut parent = Vec::with_capacity(size);
        for i in 0..size {
            parent.push(i);
        }
        UnionFind { parent }
    }

    // Add find and union methods here
    // Your code here
}

fn main() {
    let mut edges = vec![
        (0, 1, 4),
        (0, 2, 3),
        (1, 2, 1),
        (1, 3, 2),
        (2, 3, 4),
        (3, 4, 2),
        (4, 5, 6),
    ];

    // Implement Kruskal's algorithm core logic here
    // Your code here
}

Hint

Implement find with path compression and union to join sets. Sort edges and pick edges that connect different sets.

4

Print the MST edges and total cost

Add code to calculate the total weight of edges in mst. Then print each edge in the format "Edge: u - v, weight: w" and finally print the total cost as "Total cost: X".

DSA Rust

struct UnionFind {
    parent: Vec,
}

impl UnionFind {
    fn new(size: usize) -> Self {
        let mut parent = Vec::with_capacity(size);
        for i in 0..size {
            parent.push(i);
        }
        UnionFind { parent }
    }

    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 root_x = self.find(x);
        let root_y = self.find(y);
        if root_x == root_y {
            return false;
        }
        self.parent[root_y] = root_x;
        true
    }
}

fn main() {
    let mut edges = vec![
        (0, 1, 4),
        (0, 2, 3),
        (1, 2, 1),
        (1, 3, 2),
        (2, 3, 4),
        (3, 4, 2),
        (4, 5, 6),
    ];

    edges.sort_by_key(|k| k.2);
    let mut uf = UnionFind::new(6);
    let mut mst = Vec::new();

    for &(u, v, w) in &edges {
        if uf.union(u, v) {
            mst.push((u, v, w));
        }
    }

    // Print MST edges and total cost
    // Your code here

Hint

Use iter().map() to sum weights and println! to show edges and total cost.

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