Lesson 4 � Intermediate

Minimum Spanning Tree (Prim's & Kruskal's)

Minimum Spanning Tree (MST) ek aisa subset hai edges ka jo sab nodes ko connect karein bina cycle ke aur total weight minimum ho. Do famous algorithms hain � Prim's aur Kruskal's.

MST kya hota hai?

Ek weighted undirected graph hai. MST ek subgraph hai jismein:

• Sab vertices included hain
• Sab nodes connected hain (ek hi component)
• Koi cycle nahi hai (tree property)
• Total edge weight minimum hai

Important property: V vertices ke graph mein MST mein exactly V-1 edges honge.

Original Graph: MST (highlighted = bold):
 1 
 A---B 6 A---B
 | /| | 
 3 5 2 3 
 | / | | 
 C---D C---D
 4 total = 1+2+3+4 = 10

Cut Property

MST ka fundamental property: kisi bhi cut (graph ka do parts mein divide karna) ke liye, sabse kam weight wala edge jo cut cross karta hai, woh MST mein zaroor hoga.

Yeh dono algorithms ka basis hai � har step par sabse kam weight wala safe edge choose karte hain.

Prim's Algorithm � Growing Tree Approach

Prim's ek tree grow karta hai. Ek node se start karo, phir har baar sabse kam weight wala edge jo tree mein nahi hai use add karo.

Jaise ek web series ka plot grow hota hai � ek character se start hota hai aur naye characters judte jaate hain.

import heapq

def prim(graph, n):
 mst = []
 visited = set([0])
 edges = [(w, 0, to) for to, w in graph[0]]
 heapq.heapify(edges)
 
 while edges and len(mst) < n - 1:
 w, frm, to = heapq.heappop(edges)
 if to not in visited:
 visited.add(to)
 mst.append((frm, to, w))
 for nxt, wt in graph[to]:
 if nxt not in visited:
 heapq.heappush(edges, (wt, to, nxt))
 
 return mst

Kruskal's Algorithm � Sorting Edges

Kruskal's sab edges ko weight ke according sort karta hai, phir chota se chota edge pick karta hai � jab tak cycle na bane.

Cycle detect karne ke liye Union-Find data structure use hota hai.

def find(parent, x):
 if parent[x] != x:
 parent[x] = find(parent, parent[x])
 return parent[x]

def union(parent, rank, x, y):
 px, py = find(parent, x), find(parent, y)
 if px == py:
 return False # cycle hai
 if rank[px] < rank[py]:
 px, py = py, px
 parent[py] = px
 if rank[px] == rank[py]:
 rank[px] += 1
 return True

def kruskal(edges, n):
 edges.sort() # weight ke according sort
 mst = []
 parent = list(range(n))
 rank = [0] * n
 
 for w, u, v in edges:
 if union(parent, rank, u, v):
 mst.append((u, v, w))
 if len(mst) == n - 1:
 break
 
 return mst

Prim's vs Kruskal's

• Prim's: Dense graphs ke liye better. Ek node se grow karta hai. Adjacency list ke saath O(E log V).
• Kruskal's: Sparse graphs ke liye better. Sab edges sort karta hai. O(E log E) ya O(E log V).
• Dono greedy hain aur same MST dete hain (agar unique nahi hai toh alag MST ho sakte hain par same weight).

Try it: code khud likho

Edges (weight, u, v):
(1, 0, 1), (3, 0, 2), (2, 1, 2), (4, 1, 3), (5, 2, 3)
4 vertices (0, 1, 2, 3)

Common mistakes

• MST mein V-1 se zyada edges add karna � cycle ban jayegi.
• Kruskal's mein edges sort karna bhool jaana � galat MST aayega.
• Prim's mein visited check karna bhool jaana � infinite loop mein phas jaoge.
• Directed graph par MST lagana � MST sirf undirected graphs ke liye hai.
• Union-Find mein path compression ya union by rank nahi lagana � time complexity kharab ho jayegi.