Minimum spanning tree

Question 1

What is a Minimum Spanning Tree?

Answer 1

Finds minimum-weight tree connecting all nodes.

Use Case: Network design, clustering.

Example: Kruskal’s Algorithm.

Question 2

What are the key steps to find a Minimum Spanning Tree?

Answer 2

1. Sort edges by weight.
2. Use Union Find to add edges, avoid cycles.
3. Stop when n-1 edges added.

Explain steps for Kruskal’s Algorithm aloud.

Question 3

How does it apply to Kruskal’s Algorithm?

Answer 3

Problem: Find minimum spanning tree.
Approach: Sort edges, add to tree using Union Find.

Example: Kruskal’s Algorithm.

Question 4

What are the complexity and gotchas of Minimum Spanning Tree?

Answer 4

Complexity: Time: O(E log E), Space: O(V).
Gotchas: Disconnected graph, negative weights.

List edge cases for Kruskal’s Algorithm aloud.

Question 5

Code example of Minimum Spanning Tree.

Answer 5

```python
from typing import List
class UnionFind:
def __init__(self, size: int) -> None:
self.parent = list(range(size))
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -> bool:
if self.find(x) == self.find(y):
return False
self.parent[self.find(x)] = self.find(y)
return True
def kruskal(n: int, edges: List[List[int]]) -> int:
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
total_weight = 0
for u, v, weight in edges:
if uf.union(u, v):
total_weight += weight
return total_weight
~~~