Graph Algorithms
Kruskal's Algorithm & Dijkstra's Algorithm
Simple Guide — Concepts, Diagrams & Examples
Contents
1. Graph kya hota hai?
2. Kruskal's Algorithm — Sabse Sasta Connection
3. Union-Find — Kruskal ka Secret Weapon
4. Kruskal's Step-by-Step Example
5. Dijkstra's Algorithm — Shortest Raasta
6. Relaxation — Dijkstra ka Secret Weapon
7. Dijkstra's Step-by-Step Example
8. Dono ka Comparison
9. Real Life Uses
10. Exam Ke Liye Yaad Rakhne Wali Cheezein
1. Graph Kya Hota Hai?
Graph ek aisi drawing hoti hai jisme:
• Nodes (ya Vertices) — yeh circles hote hain, cities, computers, ya koi bhi jagah represent
karte hain
• Edges — yeh lines hoti hain jo nodes ko connect karti hain
• Weights — har line pe ek number hota hai, jaise distance ya cost
Example — 4 Cities ka Graph:
[Lahore]
/ \
4 2
/ \
[Multan] [Islamabad]
\ /
3 5
\ /
[Karachi]
Numbers = Road ki distance (km ya cost)
In cities ko minimum cost pe connect karna chahte hain — isi ke liye Kruskal's Algorithm hai!
Source se destination tak fastest raasta dhoondhna chahte hain — isi ke liye Dijkstra's Algorithm
hai!
2. Kruskal's Algorithm
Kisne Banaya?
Joseph Kruskal ne 1956 mein banaya. Problem thi: telephone company ko cities mein cable dalni
thi. Cable daalna expensive tha. Goal tha — sabhi cities ko connect karo, lekin minimum cable use
karo!
Simple Shabdon Mein Kya Karta Hai?
"Sabse sasti edge pehle lo, cycle mat banao, jab tak sab connect na ho."
Iska naam hai:
• MST = Minimum Spanning Tree
• Minimum = total cost sabse kam
• Spanning = sabhi nodes cover honge
• Tree = koi loop/cycle nahi hoga
MST Rules:
Rule 1: Sabhi nodes connected hone chahiye
Rule 2: Koi cycle/loop nahi honi chahiye
Rule 3: Total weight (cost) minimum hona chahiye
V nodes hain => MST mein exactly V-1 edges honge
3. Union-Find — Kruskal Ka Secret Weapon
Kruskal ko ek cheez check karni padti hai: "Agar main yeh edge add karoon, toh cycle toh nahi
banega?"
Iske liye Union-Find use hota hai. Bahut simple hai!
Union-Find Kaise Kaam Karta Hai?
Socho har node apna ek "group" hai. Shuru mein sab alag-alag hain:
Shuru mein:
Node: A B C D
Group: A B C D (sab apne group mein akele)
A-B edge add ki:
Node: A B C D
Group: A A C D (B ab A ke group mein)
C-D edge add ki:
Node: A B C D
Group: A A C C (D ab C ke group mein)
A-C edge add karein?
Group(A) = A, Group(C) = C => ALAG HAIN => ADD KAR DO!
A-B edge dobara add karein?
Group(A) = A, Group(B) = A => SAME HAIN => CYCLE BANEGA =>
SKIP!
Simple rule:
• Groups same hain — edge skip karo (cycle banega)
• Groups alag hain — edge add karo, groups merge karo
4. Kruskal's Step-by-Step Example
Yeh graph lo — 5 nodes, 7 edges:
[A]
/ | \
4/ | \2
/ |3 \
[B] | [D]
\ | /
5\ | /1
\ | /
[C]
Edges: A-D=2, A-B=4, A-C=3, C-D=1, B-C=5, B-D=6, C-A=3
Step 1: Edges ko Saste Se Mahenge Order Mein Likho
# Edge Weight
1. C-D 1 (sabse sasta!)
2. A-D 2
3. A-C 3
4. A-B 4
5. B-C 5
6. B-D 6 (sabse mehanga)
Step 2: Har Edge Check Karo
Groups shuru mein: A={A} B={B} C={C} D={D}
Edge C-D (weight 1):
C aur D alag group mein hain => ADD KAR DO [cost=1]
Groups: A={A} B={B} C,D={C,D}
Edge A-D (weight 2):
A aur D alag group mein hain => ADD KAR DO [cost=3]
Groups: B={B} A,C,D={A,C,D}
Edge A-C (weight 3):
A aur C SAME group mein hain => SKIP (cycle banega!)
Edge A-B (weight 4):
A aur B alag group mein hain => ADD KAR DO [cost=7]
Groups: A,B,C,D={A,B,C,D} (sab ek group mein!)
V-1 = 4 edges add ho gaye => MST COMPLETE!
Final MST:
[A]
/ |
4 |
/ |2
[B] |
|
[D]---1---[C]
MST Edges: C-D(1) + A-D(2) + A-B(4) = 7 (minimum total cost!)
5. Dijkstra's Algorithm
Kisne Banaya?
Edsger Dijkstra ne 1956 mein banaya — sirf 20 minute mein pencil-paper pe! Woh Rotterdam se
Groningen ka shortest route dhoondhna chahte the. Unhone socha: "Sabse paas wali jagah pehle
jaao, phir uske neighbours ko update karo."
Simple Shabdon Mein Kya Karta Hai?
"Source se shuru karo, sabse paas wala node pehle process karo, sabhi nodes ki distance update
karte jao."
Output kya milta hai? Ek distance table:
Source = City A se:
A se A ka distance = 0
A se B ka distance = 3 km
A se C ka distance = 7 km
A se D ka distance = 9 km
Yeh sab shortest distances hain!
Important baat: Dijkstra sirf tab kaam karta hai jab sab weights POSITIVE hoon (0 ya usse zyada).
Negative numbers? Toh alag algorithm chahiye.
6. Relaxation — Dijkstra Ka Secret Weapon
"Relaxation" matlab: kya is node ke through jaana zyada fast/cheap hai?
Ek chhota example:
A ---5km--- B ---3km--- C
Shuru mein:
dist[A] = 0 dist[B] = infinity dist[C] = infinity
A process hota hai:
B ko check karo: 0 + 5 = 5 < infinity => dist[B] = 5
(update!)
B process hota hai:
C ko check karo: 5 + 3 = 8 < infinity => dist[C] = 8
(update!)
Final: A=0, B=5, C=8 (ye sab shortest distances hain)
Relaxation formula (simple words mein):
Purana distance vs Naya raasta:
Agar (current node ki distance + edge weight) < neighbour ki
distance
Toh neighbour ki distance update karo
Matlab: kya yahan se jaana zyada sasta/fast hai?
7. Dijkstra's Step-by-Step Example
Yeh graph lo — Source = A:
[A]
/ \
4 2
/ \
[B] [C]
\ /
3 1
\ /
[D]
Edges: A-B=4, A-C=2, C-B=1, C-D=5, B-D=3
Step 1: Shuru Karo
dist[A]=0 dist[B]=inf dist[C]=inf dist[D]=inf
Visited: koi nahi
Step 2: Sabse Kam Distance Wala Node Lo = A (dist=0)
A ke neighbours:
B: dist[A] + 4 = 0+4 = 4 < inf => dist[B] = 4
(update!)
C: dist[A] + 2 = 0+2 = 2 < inf => dist[C] = 2
(update!)
dist[A]=0 dist[B]=4 dist[C]=2 dist[D]=inf
A visited mark ho gaya.
Step 3: Abhi Sabse Kam = C (dist=2)
C ke neighbours:
B: dist[C] + 1 = 2+1 = 3 < 4 => dist[B] = 3
(better path mila!)
D: dist[C] + 5 = 2+5 = 7 < inf => dist[D] = 7
(update!)
dist[A]=0 dist[B]=3 dist[C]=2 dist[D]=7
C visited mark ho gaya.
Step 4: Abhi Sabse Kam = B (dist=3)
B ke neighbours:
D: dist[B] + 3 = 3+3 = 6 < 7 => dist[D] = 6
(better path!)
dist[A]=0 dist[B]=3 dist[C]=2 dist[D]=6
B visited mark ho gaya.
Step 5: D (dist=6) — Last Node
D ke koi unvisited neighbours nahi => Done!
FINAL ANSWER:
A se A = 0 (khud)
A se C = 2 (A -> C)
A se B = 3 (A -> C -> B)
A se D = 6 (A -> C -> B -> D)
Note: A-B direct jaate toh 4 lagta. C ke through jaane se sirf
3!
8. Dono Ka Comparison
Feature Kruskal's Dijkstra's
Goal Sabhi nodes minimum cost Source se sabhi tak shortest
pe connect karo path nikalo
Problem Type Minimum Spanning Tree Shortest Path (SSSP)
(MST)
Secret Weapon Union-Find (cycle check) Min-Heap (nearest node
first)
Output Ek tree jisme V-1 edges Distance table (source se
hain har node tak)
Negative Edges Allowed hain Nahi chalta (sirf positive
weights)
Time Complexity O(E log E) O((V+E) log V)
Invented By Joseph Kruskal, 1956 Edsger Dijkstra, 1956
Desi Analogy Mein Yaad Rakho:
KRUSKAL'S DIJKSTRA'S
Colony mein ek baar wiring kar raha hai. Ghar se office jaana hai. Google Maps
Minimum wire lagao taake sab ke ghar kholte ho aur fastest route dhoondhte
bijli pahunche. Ek baar karo, hamesha ho. Har baar traffic ke hisaab se
ke liye sab connected! best path milta hai.
=> Infrastructure banana => Navigation / Routing
9. Real Life Mein Kahan Use Hota Hai?
Kruskal's Algorithm:
• Telephone cables — minimum wire lagake sabhi offices connect karna
• Internet backbone — routers ke beech minimum cable cost
• Road planning — cities ko connect karne wali minimum roads banana
• Water/Gas pipeline — minimum pipe lagake pura colony cover karna
• Machine Learning — data ko groups (clusters) mein divide karna
Dijkstra's Algorithm:
• Google Maps / GPS — source se destination ka shortest ya fastest route
• Internet Routing — data packets best route se travel karte hain (OSPF protocol)
• Game Development — game characters sabse fast path dhoondh ke chalte hain
• Social Networks — do logon ke beech minimum degree of separation
• Flight booking apps — cheapest flight route nikalna
10. Exam Ke Liye Yaad Rakhne Wali Cheezein
Kruskal's — Quick Reminder:
Question mein yeh words dikhen toh Kruskal:
'MST', 'Minimum Spanning Tree', 'minimum cost to connect all
nodes'
Steps yaad karne ka tarika:
SORT -> CHECK CYCLE -> ADD/SKIP -> REPEAT
V = total nodes => MST mein V-1 edges honge (hamesha!)
Cycle check: Find(u) == Find(v) => SKIP | Find(u) !=
Find(v) => ADD
Dijkstra's — Quick Reminder:
Question mein yeh words dikhen toh Dijkstra:
'Shortest path', 'minimum distance from source', 'SSSP'
Steps yaad karne ka tarika:
INITIALIZE -> PICK MIN -> RELAX NEIGHBOURS -> MARK VISITED ->
REPEAT
Negative weights? => Dijkstra FAIL! Use Bellman-Ford instead.
Relaxation: agar (dist[u] + weight) < dist[v] => dist[v] ko
update karo
Dono Mein Farq — Ek Nazar Mein:
KRUSKAL = Infrastructure = Sab ko connect karo = Union-
Find
DIJKSTRA = Navigation = Shortest raasta nikalo = Min-
Heap
Ab yeh algorithms clear hain? Agar koi step samajh na aaye, dobara padho aur example trace karo!