🌲 MST Fundamentals

🎯 What is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) of a connected, undirected graph is a subgraph that is a tree (connected, acyclic) and spans all vertices, with the minimum possible total edge weight.

Spanning Tree: Connects all vertices with |V| - 1 edges
Minimum: Sum of edge weights is minimized
Graph: Connected, undirected, weighted
Key Insight: MST is unique if all edge weights are distinct

📌 Cut Property📌 Cycle Property📌 Greedy Algorithms

The Core Insight

Key Insight: An MST is a "minimum cost" way to connect all vertices. This is a fundamental problem in network design with numerous applications.

Two Main Algorithms:

Prim's Algorithm Grows tree from a starting vertex
Kruskal's Algorithm Adds edges in increasing weight order

# MST Problem Statement
# Given: Connected undirected graph G = (V, E) with weights
# Find: Tree T ⊆ E such that:
#   1. T connects all vertices (V)
#   2. T has |V| - 1 edges (no cycles)
#   3. Sum of weights in T is minimized

# Example:
# Vertices: A, B, C, D
# Edges: A-B(1), B-C(2), C-D(3), A-D(4), A-C(5)
# MST: A-B(1), B-C(2), C-D(3) → Total weight: 6

📐 MST Properties

🎯 Fundamental Theorems

Cut Property: For any cut, the minimum weight edge crossing the cut belongs to some MST
Cycle Property: For any cycle, the maximum weight edge in the cycle does not belong to any MST
Uniqueness: If all edge weights are distinct, the MST is unique
Subtree Property: Any subtree of an MST is also a MST of the subgraph it spans

# Cut Property Demonstration
# Partition vertices into two sets S and V-S
# The minimum weight edge between S and V-S is in some MST

# Cycle Property Demonstration
# Any cycle in the graph: the maximum weight edge in the cycle
# is NOT in any MST

# Example:
# Graph with cycle: A-B(5), B-C(3), A-C(4)
# Cycle: A-B-C-A
# Maximum edge: A-B(5) → Not in MST
# MST: A-C(4) + B-C(3) = 7

🔵 Prim's Algorithm

🎯 Growing the Tree from a Start Vertex

Prim's algorithm grows the MST by adding the cheapest edge that connects a vertex in the tree to a vertex outside the tree.

Approach: Start with any vertex, grow the tree
Data Structure: Priority queue (min-heap) for edge weights
Time: O(E log V) with binary heap
Space: O(V)

# Prim's Algorithm Implementation
import heapq

def prims_algorithm(graph, start=0):
    n = len(graph)
    visited = [False] * n
    min_heap = [(0, start, -1)]  # (weight, vertex, parent)
    mst_weight = 0
    mst_edges = []
    
    while min_heap:
        weight, u, parent = heapq.heappop(min_heap)
        
        if visited[u]:
            continue
        
        visited[u] = True
        mst_weight += weight
        
        if parent != -1:
            mst_edges.append((parent, u, weight))
        
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (w, v, u))
    
    return mst_weight, mst_edges

# Example Graph (Adjacency List)
# graph = [
#     [(1, 2), (3, 6)],     # 0: A
#     [(0, 2), (2, 3), (3, 8)], # 1: B
#     [(1, 3), (3, 5)],     # 2: C
#     [(0, 6), (1, 8), (2, 5)]  # 3: D
# ]
# MST Weight: 2 + 3 + 5 = 10
# Edges: (0-1,2), (1-2,3), (2-3,5)

🔴 Kruskal's Algorithm

🎯 Adding Edges in Sorted Order

Kruskal's algorithm sorts all edges by weight and adds them one by one if they don't create a cycle.

Approach: Process edges in increasing weight order
Key Component: Disjoint Set Union (DSU) for cycle detection
Time: O(E log E) for sorting + O(E α(V)) for DSU
Space: O(V + E)

# Kruskal's Algorithm Implementation
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

def kruskal_algorithm(n, edges):
    # edges: list of (weight, u, v)
    edges.sort()
    dsu = DSU(n)
    mst_weight = 0
    mst_edges = []
    
    for weight, u, v in edges:
        if dsu.union(u, v):
            mst_weight += weight
            mst_edges.append((u, v, weight))
            if len(mst_edges) == n - 1:
                break
    
    return mst_weight, mst_edges

# Example:
# edges = [(2, 0, 1), (3, 1, 2), (5, 2, 3), (6, 0, 3), (8, 1, 3)]
# MST Weight: 2 + 3 + 5 = 10

🔗 Disjoint Set Union (DSU)

🎯 Union-Find Data Structure

DSU is the key component in Kruskal's algorithm. It efficiently tracks which vertices are in the same component.

Find: Find the representative of a set (with path compression)
Union: Merge two sets (with union by rank/size)
Time: Almost O(1) (inverse Ackermann function)
Space: O(V)

# Disjoint Set Union - Full Implementation
class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n
    
    def find(self, x):
        # Path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        
        # Union by size
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        self.components -= 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)

# Key optimizations:
# 1. Path compression: Flatten the tree during find
# 2. Union by size/rank: Attach smaller tree to larger

⚖️ Prim vs Kruskal

Feature	Prim's Algorithm	Kruskal's Algorithm
Approach	Vertex-based (grows tree)	Edge-based (adds edges)
Data Structure	Priority Queue (Min-Heap)	Disjoint Set Union (DSU)
Time Complexity	O(E log V)	O(E log E)
Space Complexity	O(V)	O(V + E)
Best for	Dense graphs	Sparse graphs
Implementation	More complex with heap	Simpler with DSU
Component handling	Single component grows	Multiple components merge
Parallelization	Harder	Easier

⏱️ Time & Space Complexities

Algorithm	Time Complexity	Space Complexity	Notes
Prim (Binary Heap)	O(E log V)	O(V)	Best for dense graphs
Prim (Fibonacci Heap)	O(E + V log V)	O(V)	Theoretical optimum
Kruskal	O(E log E)	O(V + E)	Best for sparse graphs
Borůvka	O(E log V)	O(V + E)	Parallelizable
Kruskal (Sorting)	O(E log E)	O(1)	Sorting dominates
DSU Operations	O(α(V))	O(V)	Almost constant

🌀 MST Variations

Maximum Spanning Tree: Maximize total weight (negate weights)
Second Best MST: Find second minimum MST
Minimum Spanning Forest: For disconnected graphs
Minimum Bottleneck Spanning Tree: Minimize the maximum edge weight
Directed MST (Arborescence): Edmonds' algorithm
Steiner Tree: MST that includes only required vertices
Degree-Constrained MST: Limit vertex degree
Euclidean MST: MST of points in Euclidean space

🔷 Borůvka's Algorithm

🎯 Parallel MST Algorithm

Borůvka's algorithm is the oldest MST algorithm. It repeatedly adds the minimum outgoing edge from each component, merging components.

Approach: For each component, find the minimum weight edge to another component
Time: O(E log V)
Parallelization: All components can be processed in parallel
Used in: Distributed MST algorithms

# Borůvka's Algorithm
def boruvka_algorithm(n, edges):
    dsu = DSU(n)
    mst_weight = 0
    mst_edges = []
    
    # edges: list of (u, v, weight)
    while len(mst_edges) < n - 1:
        # Find minimum outgoing edge for each component
        min_edge = {i: None for i in range(n)}
        
        for u, v, w in edges:
            ru, rv = dsu.find(u), dsu.find(v)
            if ru == rv:
                continue
            
            if min_edge[ru] is None or w < min_edge[ru][2]:
                min_edge[ru] = (u, v, w)
            if min_edge[rv] is None or w < min_edge[rv][2]:
                min_edge[rv] = (u, v, w)
        
        # Add all minimum edges
        for u, v, w in min_edge.values():
            if u is not None and dsu.union(u, v):
                mst_weight += w
                mst_edges.append((u, v, w))
    
    return mst_weight, mst_edges

# Example:
# n = 4
# edges = [(0,1,2), (0,3,6), (1,2,3), (1,3,8), (2,3,5)]
# MST Weight: 2 + 3 + 5 = 10

🥈 Second Best MST

🎯 Finding the Next Best Tree

The second best MST is the MST with the second minimum total weight (or a different tree with the next minimum weight).

Approach: Find MST, then find best replacement edge
Key Idea: Replace one edge in the MST with a non-MST edge
Time: O(E log V) for MST + O(V²) for maximum edge in paths

# Second Best MST
def second_best_mst(n, edges):
    # Step 1: Find MST using Kruskal
    edges.sort()
    mst_edges = []
    mst_weight = 0
    dsu = DSU(n)
    
    for w, u, v in edges:
        if dsu.union(u, v):
            mst_edges.append((u, v, w))
            mst_weight += w
    
    # Step 2: Build adjacency list of MST
    mst_adj = [[] for _ in range(n)]
    for u, v, w in mst_edges:
        mst_adj[u].append((v, w))
        mst_adj[v].append((u, w))
    
    # Step 3: Find maximum edge on path between any two vertices
    # (Simplified approach: DFS from each vertex)
    def dfs_max_path(start):
        max_edge = [0] * n
        stack = [(start, -1, 0)]
        while stack:
            u, parent, max_w = stack.pop()
            max_edge[u] = max_w
            for v, w in mst_adj[u]:
                if v != parent:
                    stack.append((v, u, max(max_w, w)))
        return max_edge
    
    # Step 4: Try replacing each non-MST edge
    best = float('inf')
    for w, u, v in edges:
        if (u, v, w) not in mst_edges and (v, u, w) not in mst_edges:
            # Find max edge on path u-v in MST
            max_on_path = dfs_max_path(u)[v]
            # Try replacing
            candidate = mst_weight - max_on_path + w
            if candidate > mst_weight:  # Must be strictly greater
                best = min(best, candidate)
    
    return best

📈 Maximum Spanning Tree

🎯 Maximizing Total Weight

The Maximum Spanning Tree (MaxST) is the spanning tree with the maximum possible total edge weight. It's useful for maximizing connectivity benefits.

Approach: Negate all edge weights and find MST
Or: Sort edges in descending order for Kruskal
Properties: Same algorithms, just reverse the sorting

# Maximum Spanning Tree
def maximum_spanning_tree(n, edges):
    # Approach 1: Negate weights and use MST
    neg_edges = [(-w, u, v) for w, u, v in edges]
    return kruskal_algorithm(n, neg_edges)

# Approach 2: Sort in descending order
def max_spanning_tree_kruskal(n, edges):
    # edges: list of (weight, u, v)
    edges.sort(reverse=True)  # Descending order
    dsu = DSU(n)
    max_weight = 0
    max_edges = []
    
    for weight, u, v in edges:
        if dsu.union(u, v):
            max_weight += weight
            max_edges.append((u, v, weight))
            if len(max_edges) == n - 1:
                break
    
    return max_weight, max_edges

# Example:
# Graph with edges: (1, A-B), (5, B-C), (3, A-C)
# MaxST: A-C(3) + B-C(5) = 8

🌍 Real-World Applications

Network Design: Connecting computers with minimum cable
Telecommunications: Laying fiber optic networks
Transportation: Building roads between cities
Power Grid: Designing electrical distribution
Cluster Analysis: Single-linkage clustering (MST)
Circuit Design: Minimizing wire length
Game Development: Procedural map generation
Bioinformatics: Phylogenetic trees

🧠 Advanced MST Concepts

Online MST: Building MST when vertices arrive dynamically
MST in Dynamic Graphs: Updates to edges (add/delete)
Minimum Label Spanning Tree: Minimize number of distinct labels
Bottleneck Spanning Tree: Minimize maximum edge weight
MST in Complete Graphs: Specialized algorithms for dense graphs
MST in Planar Graphs: Properties of MST in planar graphs
MST Verification: Check if a given tree is an MST

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic: "Find MST of a given graph"
Prim vs Kruskal: "Which algorithm would you use and why?"
Minimum Cost: "Connect all cities with minimum road cost"
Network: "Minimum cost to connect all computers"
Maximum: "Find maximum spanning tree"
Second Best: "Find second best MST"
With Constraints: "MST with degree constraints"
Clustering: "Use MST for hierarchical clustering"

# Interview Problem: Connect Cities
def min_cost_to_connect_cities(n, connections):
    # connections: list of [city1, city2, cost]
    # Use Kruskal's algorithm
    edges = [(cost, u, v) for u, v, cost in connections]
    return kruskal_algorithm(n, edges)

# Interview Problem: MST with Fixed Edge
def mst_with_fixed_edge(n, edges, fixed_edge):
    # Force fixed_edge to be in the MST
    u, v, w = fixed_edge
    # Add the edge first, then continue with Kruskal
    dsu = DSU(n)
    mst_weight = w
    dsu.union(u, v)
    mst_edges = [(u, v, w)]
    
    for wt, a, b in sorted(edges):
        if (a == u and b == v) or (a == v and b == u):
            continue
        if dsu.union(a, b):
            mst_weight += wt
            mst_edges.append((a, b, wt))
    
    return mst_weight, mst_edges

# Interview Problem: Check if Edge is in MST
def is_edge_in_mst(n, edges, edge_to_check):
    # An edge is in SOME MST if there exists an MST containing it
    # Check if weight(edge) <= max edge on path in MST
    # (Using cycle property)
    u, v, w = edge_to_check
    # Get MST
    mst_weight, mst_edges = kruskal_algorithm(n, edges)
    # Find maximum edge on path u-v in MST
    # If w <= max_edge_on_path, the edge is in some MST
    pass