ایک graph vertices کا ایک مجموعہ ہے جو edges سے منسلک ہوتے ہیں۔ دو معیاری نمائندگیاں adjacency list ہیں (ہر vertex اپنے neighbors کو محفوظ کرتا ہے) اور adjacency matrix (V×V بولین کا ایک گرڈ)۔ انتخاب گراف density پر منحصر ہے۔
ایک graph vertices کا ایک مجموعہ ہے جو edges سے منسلک ہوتے ہیں۔ دو معیاری نمائندگیاں adjacency list ہیں (ہر vertex اپنے neighbors کو محفوظ کرتا ہے) اور adjacency matrix (V×V بولین کا ایک گرڈ)۔ انتخاب گراف density پر منحصر ہے۔
Graph: 0 - 1
| |
2 - 3
Adjacency list: Adjacency matrix:
0: [1, 2] 0 1 2 3
1: [0, 3] 0 [0 1 1 0]
2: [0, 3] 1 [1 0 0 1]
3: [1, 2] 2 [1 0 0 1]
3 [0 1 1 0]
# Adjacency list (dict of lists) — preferred for sparse graphs
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1] # O(1) to get a vertex's neighbors
# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1 # O(1) edge lookup
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Edge exists? | O(degree) | O(1) |
| Iterate neighbors | O(degree) | O(V) |
| Best for | sparse graphs | dense graphs |
زیادہ تر حقیقی دنیا کے گرافس (social networks، road maps، dependency graphs) sparse ہوتے ہیں، اس لیے adjacency lists بہت زیادہ space بچاتے ہیں اور BFS/DFS جیسے traversals کو تیز کرتے ہیں۔ radeoff کو جاننا آپ کو ایسی نمائندگی منتخب کرنے کی اجازت دیتا ہے جو آپ کے گراف algorithms کو موثر رکھے بجائے اس کے کہ غیر ارادی طور پر O(V²) memory استعمال کریں۔