Minimum Spanning Tree (Kruskal)

▶

Steps

setup

Sort edges by weight ascending

The algorithm begins by sorting all edges by their weight in ascending order to ensure the smallest edges are considered first.

💡 Sorting edges is crucial because Kruskal's algorithm always picks the smallest edge that doesn't form a cycle.

Line:

edges.sort(key=lambda x: x[2])

💡 Edges are now ordered to process from smallest to largest weight.

setup

Initialize Union-Find structure

Create a Union-Find data structure with each node as its own parent and size 1, representing separate sets initially.

💡 Union-Find helps efficiently check if adding an edge creates a cycle by tracking connected components.

Line:

uf = UnionFind(n)

💡 Each node is initially in its own set, so no edges are connected yet.

compare

Consider edge (0,1) with weight 1

The algorithm picks the smallest edge (0,1) and attempts to union their sets to add this edge to the MST.

💡 This step tests if adding this edge creates a cycle or connects two separate components.

Line:

if uf.union(u, v):

💡 Edge (0,1) can be safely added to MST as it connects two distinct sets.

insert

Add edge weight 1 to MST total

Since union succeeded, add the edge weight 1 to the MST total weight and increment edges used count.

💡 Accumulating the MST weight tracks the total cost of the spanning tree being built.

Line:

mst_weight += w
edges_used += 1

💡 MST weight is now 1 after adding the first edge.

compare

Consider edge (1,2) with weight 2

Next edge (1,2) is considered. The algorithm tries to union sets containing nodes 1 and 2.

💡 This tests if adding edge (1,2) connects two different components or forms a cycle.

Line:

if uf.union(u, v):

💡 Edge (1,2) connects two distinct sets and can be added to MST.

insert

Add edge weight 2 to MST total

Add the weight 2 of edge (1,2) to the MST total and increment edges used count.

💡 This updates the MST cost as the tree grows.

Line:

mst_weight += w
edges_used += 1

💡 MST weight is now 3 after adding edges (0,1) and (1,2).

compare

Consider edge (0,2) with weight 3

Consider edge (0,2). The algorithm tries to union sets containing nodes 0 and 2.

💡 This tests if adding edge (0,2) would create a cycle or connect different sets.

Line:

if uf.union(u, v):

💡 Edge (0,2) would create a cycle and is therefore skipped.

compare

Consider edge (2,3) with weight 4

Consider edge (2,3). The algorithm tries to union sets containing nodes 2 and 3.

💡 This tests if adding edge (2,3) connects two different sets or forms a cycle.

Line:

if uf.union(u, v):

💡 Edge (2,3) connects two distinct sets and can be added to MST.

insert

Add edge weight 4 to MST total

Add the weight 4 of edge (2,3) to the MST total and increment edges used count.

💡 This completes the MST by connecting all nodes with minimal total weight.

Line:

mst_weight += w
edges_used += 1

💡 MST weight is now 7 after adding edges (0,1), (1,2), and (2,3).

prune

Stop: MST complete with n-1 edges

Since the MST now contains n-1=3 edges, the algorithm stops and returns the total MST weight.

💡 The MST is complete when all nodes are connected with minimal total edge weight.

Line:

if edges_used == n - 1:
    break

💡 The MST weight 7 is the minimal sum connecting all nodes without cycles.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # STEP 2
        self.size = [1] * n          # STEP 2

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # Path compression
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # STEP 7 decision: cycle detected
        if self.size[rx] < self.size[ry]:
            self.parent[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.parent[ry] = rx
            self.size[rx] += self.size[ry]
        return True  # STEP 3,5,8 decision: union succeeded

def kruskal_mst_union_by_size(n, edges):
    edges.sort(key=lambda x: x[2])  # STEP 1
    uf = UnionFind(n)               # STEP 2
    mst_weight = 0
    edges_used = 0
    for u, v, w in edges:
        if uf.union(u, v):           # STEP 3,5,7,8
            mst_weight += w          # STEP 4,6,9
            edges_used += 1
            if edges_used == n - 1: # STEP 10
                break
    return mst_weight

if __name__ == '__main__':
    n = 4
    edges = [(0,1,1),(1,2,2),(0,2,3),(2,3,4)]
    print(kruskal_mst_union_by_size(n, edges))  # Output: 7

📊

Minimum Spanning Tree (Kruskal) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how union-find efficiently prevents cycles and how the MST grows by adding the smallest edges that connect disjoint sets.

Visiting: none

0

1

2

3

Queue / Stack

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

Visiting: none

0

1

2

3

Queue / Stack

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

Visiting: 0

Edge: 0 → 1

0

1

2

3

Queue / Stack

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

Visiting: none

0

1

2

3

Queue / Stack

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

Visiting: 2

Edge: 1 → 2

0

1

2

3

Queue / Stack

(0,2,3)(2,3,4)

Visiting: none

0

1

2

3

Queue / Stack

(0,2,3)(2,3,4)

Visiting: none

Edge: 0 → 2

0

1

2

3

Queue / Stack

(2,3,4)

Visiting: 3

Edge: 2 → 3

0

1

2

3

Visiting: none

0

1

2

3

Visiting: none

0

1

2

3

Key Takeaways

✓ Kruskal's algorithm relies on sorting edges by weight to ensure the MST is minimal.

This insight is hard to see from code alone because sorting is a separate step that affects the entire process.

✓ Union-Find efficiently detects cycles by checking if two nodes belong to the same set before union.

Visualizing union-find operations clarifies how path compression and union by size optimize the process.

✓ Edges that would create cycles are skipped, and the MST grows by connecting disjoint sets until all nodes are connected.

Seeing the decision to reject an edge due to cycle detection helps understand the pruning logic.

Practice

1. Given the following code snippet implementing the union-find approach for Swim in Rising Water, and the input grid:

grid = [
  [0, 2],
  [1, 3]
]

# After sorting cells by elevation, what is the earliest time returned by swimInWater(grid)?

What is the returned value?

easy

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Sort cells by elevation

   Sorted cells: (0,0,0), (1,1,0), (2,0,1), (3,1,1)

2. Step 2: Union adjacent cells with elevation ≤ current

   At elevation=0, only (0,0) is active; no union with end. At elevation=1, union (1,0) with (0,0) possible. At elevation=2, union (0,1) with (0,0) or (1,0). At elevation=3, union (1,1) with neighbors, connecting start and end.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Earliest time when start and end connected is elevation 3 [OK]

Hint: Trace union-find merges in elevation order [OK]

Common Mistakes:

• Returning elevation before union-find connects start and end
• Confusing cell indices or union conditions
• Off-by-one errors in elevation comparisons

2. The following code attempts to find a redundant connection using union-find but contains a subtle bug. Identify the line causing incorrect behavior.

medium

A. Line setting parent[i] = i in the for loop

B. Line incrementing rank[rootA] after union

C. Line checking if rootA == rootB in union function

D. Line initializing parent with zeros: parent = [0]*(n+1)

Solution

1. Step 1: Analyze parent array initialization

   Initializing parent with zeros causes all nodes to initially point to 0, which is incorrect for 1-based nodes.

2. Step 2: Check for correct parent assignment

   The for loop tries to fix this, but if n=0, loop may not run properly or indexing may be off; better to initialize parent as list(range(n+1)) directly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect parent initialization leads to wrong find results [OK]

Hint: Parent array must be initialized to self indices [OK]

Common Mistakes:

• Forgetting to initialize parent properly
• Assuming zeros are valid parents
• Misindexing parent array

3. What is the time complexity of the optimal union-find + priority queue approach to the smallest string with swaps problem, where n is the length of the string and m is the number of pairs?

medium

A. O(n log n + m α(n)) where α(n) is the inverse Ackermann function from union-find operations

B. O(n * m) due to iterating over all pairs for each character

C. O(n²) because sorting characters in each connected component can be quadratic in worst case

D. O(m log n) because union-find operations dominate the runtime

Solution

1. Step 1: Analyze union-find operations

   Union-find performs m union/find operations in O(m α(n)) time, where α(n) is very slow growing and almost constant.

2. Step 2: Analyze sorting step

   Sorting characters in all connected components combined takes O(n log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Union-find plus sorting dominates runtime as O(n log n + m α(n)) [OK]

Hint: Union-find nearly linear; sorting dominates with n log n [OK]

Common Mistakes:

• Assuming O(n*m) due to nested loops
• Confusing sorting cost as O(n²)
• Ignoring inverse Ackermann factor

4. Suppose the problem is extended so that the input matrix isConnected can be updated dynamically with new connections added over time. Which data structure or approach is best suited to efficiently maintain and query the number of provinces after each update?

hard

A. Re-run DFS from scratch after each update to count provinces

B. Use Union-Find (Disjoint Set Union) with path compression to merge sets

C. Maintain adjacency list and run BFS only on updated nodes

D. Use a priority queue to track connected components sizes

Solution

1. Step 1: Understand dynamic updates require efficient merges

   Recomputing connected components from scratch is costly for each update.

2. Step 2: Identify data structure supporting fast union and find

   Union-Find with path compression supports near O(1) merges and queries, ideal for dynamic connectivity.

3. Step 3: Evaluate other options

   BFS or DFS on updates is expensive; priority queue does not maintain connectivity efficiently.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Union-Find is standard for dynamic connectivity problems [OK]

Hint: Dynamic connectivity -> Union-Find with path compression [OK]

Common Mistakes:

• Re-running DFS each update
• Trying BFS on partial graph

5. Suppose the problem is modified so that edges can be added multiple times (i.e., duplicate edges allowed), and you need to find the first edge that creates a cycle considering duplicates. Which modification to the union-find approach correctly handles this scenario?

hard

A. Before union, check if the edge already exists in a hash set; if yes, return it immediately as redundant

B. Use union-find as usual but also maintain a visited edges set to detect duplicates causing cycles

C. Modify union-find to count the number of times an edge is added and only detect cycle when count > 1

D. Ignore duplicates and run union-find as usual; duplicates won't affect cycle detection

Solution

1. Step 1: Understand duplicate edges impact

   Duplicate edges connect the same nodes multiple times, creating immediate cycles on second insertion.

2. Step 2: Modify algorithm to detect duplicates

   Using a hash set to track edges allows detecting duplicates before union, returning the duplicate edge as redundant immediately.

3. Step 3: Why other options fail

   Ignoring duplicates misses immediate cycle; counting edge additions in union-find is not standard; maintaining visited edges separately duplicates hash set logic.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash set lookup detects duplicates in O(1) before union [OK]

Hint: Detect duplicates with a hash set before union [OK]

Common Mistakes:

• Assuming union-find alone detects duplicates
• Trying to count edges in union-find
• Ignoring duplicate edges impact