Minimum Spanning Tree Kruskal's Algorithm in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree is a subset of edges in a connected, weighted graph that connects all vertices together without any cycles and with the minimum possible total edge weight.

beginner

What is the main idea behind Kruskal's Algorithm?

Kruskal's Algorithm builds the MST by sorting all edges by weight and adding them one by one to the MST, skipping edges that would form a cycle, until all vertices are connected.

intermediate

Why do we use a Disjoint Set (Union-Find) data structure in Kruskal's Algorithm?

The Disjoint Set helps quickly check if adding an edge will create a cycle by tracking which vertices are already connected, allowing efficient union and find operations.

intermediate

What is the time complexity of Kruskal's Algorithm?

The time complexity is O(E log E), where E is the number of edges, mainly due to sorting edges. Union-Find operations are almost constant time.

beginner

Show the Rust code snippet to sort edges by weight for Kruskal's Algorithm.

edges.sort_by_key(|edge| edge.weight); This sorts the vector of edges in ascending order by their weight.

What does Kruskal's Algorithm add to the MST first?

A Random edges

B Edges with the smallest weight

C Edges with the largest weight

D Edges connected to the first vertex only

Kruskal's Algorithm always picks the smallest weight edges first to ensure the total weight is minimized.

Which data structure helps Kruskal's Algorithm avoid cycles?

A Stack

B Queue

C Disjoint Set (Union-Find)

D Linked List

The Disjoint Set data structure efficiently tracks connected components to avoid cycles.

What is the stopping condition for Kruskal's Algorithm?

A When MST has (V-1) edges, where V is number of vertices

B When all edges are added

C When the graph is empty

D When all vertices have degree 2

The MST is complete when it has exactly one less edge than the number of vertices.

If adding an edge creates a cycle, what does Kruskal's Algorithm do?

A Restarts the algorithm

B Adds the edge anyway

C Removes a different edge

D Skips the edge

To keep the MST cycle-free, Kruskal's Algorithm skips edges that would create a cycle.

What is the main cost in Kruskal's Algorithm?

A Sorting edges

B Finding vertices

C Adding vertices

D Printing the MST

Sorting edges by weight is the most time-consuming step in Kruskal's Algorithm.

Explain how Kruskal's Algorithm builds a Minimum Spanning Tree step-by-step.

Think about sorting edges and checking cycles before adding.

Describe the role of the Disjoint Set (Union-Find) data structure in Kruskal's Algorithm.

Focus on how it helps avoid 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