Representations — adjacency matrix (space O(V²)), adjacency list (space O(V+E))

3.5.2 · Coding › Graphs

HUM KYA represent kar rahe hain?

Woh key fact jo saare space costs control karta hai: $0 \leq E \leq (2 V) = \frac{V ( V - 1 )}{2} = O (V^{2}) (undirected, no self-loops)$

Toh zyada se zyada $\sim V^{2} /2$ edges ho sakti hain. Jis graph mein $E \approx V^{2}$ ho use dense kehte hain; jisme $E \approx V$ ho (ya $E ≪ V^{2}$ ) use sparse kehte hain. Yahi ek distinction decide karti hai ki kaun sa representation better rahega.

Representation 1 — Adjacency Matrix

YEH $O (V^{2})$ kyun cost karti hai: hum har ordered pair $(u, v)$ ke liye ek cell allocate karte hain — yeh $V \times V = V^{2}$ cells hain — chahe actually kitni bhi edges exist karti hon. Ek empty graph bhi jisme $V = 1000$ ho woh million cells kha jaata hai.

Representation 2 — Adjacency List

YEH $O (V + E)$ kyun cost karta hai: hum $V$ list headers store karte hain ( $+ V$ ), aur saari lists milake, exactly ek entry per edge-endpoint hoti hai. Har undirected edge do lists mein appear hoti hai, toh total entries $= 2 E = O (E)$ hain. Directed: $E$ entries. Sum: $O (V + E)$ . Absent edges ke liye kuch store nahi hota — yahi saving hai.

Figure — Representations — adjacency matrix (space O(V²)), adjacency list (space O(V+E))

YEH DONO kaise compare karte hain (80/20 table)

Operation	Adjacency Matrix	Adjacency List
Space	$O (V^{2})$	$O (V + E)$
Edge query `isEdge(u,v)?`	$O (1)$ ✅	$O (de g u)$
$u$ ke saare neighbors list karo	$O (V)$ (poori row scan)	$O (de g u)$ ✅
Edge add karo	$O (1)$	$O (1)$
Saari edges iterate karo	$O (V^{2})$	$O (V + E)$ ✅
Best for	dense graphs / fast edge checks	sparse graphs (common case)

Worked Examples

Worked example Example 1 — Ek chhote undirected graph ke liye dono banao

Vertices ${0, 1, 2, 3}$ , edges ${0, 1}, {0, 2}, {1, 2}, {2, 3}$ .

Matrix (symmetric): $A = 0110101011010010$ Yeh step kyun? Row 2 (vertex 2) mein columns 0,1,3 mein 1 hain kyunki 2 unse teen vertices se touch karta hai.

List:

0 -> [1, 2]
1 -> [0, 2]
2 -> [0, 1, 3]
3 -> [2]

Yeh step kyun? Edge ${0, 1}$ dono adj[0] aur adj[1] mein appear hoti hai — undirected matlab dono directions store karo. Total entries $= 2 E = 8$ . ✔

Common Mistakes (Steel-manned)

Active Recall

Recall Quick self-test (chhupa ke jawab do)

Matrix ke liye exactly $O (V^{2})$ kyun hai chahe edges kam hon?
Undirected list mein $E$ nahi $2 E$ entries kyun hain?
Kaun sa representation isEdge(u,v) ko $O (1)$ banata hai?
Kis graph type ke liye dono ke space costs equal ho jaate hain?

Jawab: 1) har ordered pair ke liye ek cell, edges irrelevant. 2) edge dono endpoints ki lists mein store hoti hai. 3) matrix. 4) dense, $E = Θ (V^{2})$ .

Adjacency matrix space complexity

O (V^{2})

— vertices ke har ordered pair ke liye ek cell

Adjacency list space complexity

O (V + E)

—

V

headers plus

2 E

(undirected) edge entries

Matrix

O (V^{2})

kyun hai jab graph mein edges kam hon

Yeh har pair

(u, v)

ke liye cell allocate karta hai chahe edge exist kare ya na kare

Ek undirected edge kitni list entries banati hai

Do — yeh dono endpoints ke neighbor lists mein store hoti hai

Matrix mein isEdge(u,v) check karne ka time

O (1)

— direct index A[u][v]

List mein isEdge(u,v) check karne ka time

O (de g u)

— u ki neighbor list scan karni padti hai

Matrix mein u ke saare neighbors list karne ka time

O (V)

— poori row scan

List mein u ke saare neighbors list karne ka time

O (de g u)

Sparse graphs ke liye default representation

Adjacency list

Matrix ki space list ki space se kab tie karti hai

Dense graphs jahan

E = Θ (V^{2})

Undirected graph ki adjacency matrix ki property

Yeh symmetric hoti hai,

A = A^{T}

(A^{k}) [u] [v]

ka matlab

u

v

tak exactly

k

length ke walks ki count

V vertices wale undirected simple graph mein edges ki max count

(2 V) = \frac{V ( V - 1 )}{2}

Recall Feynman: 12-saal ke bachche ko explain karo

Apni class imagine karo aur socho kaun kaun se dost hain. Method 1 (grid / matrix): ek bada checkerboard banao jisme har bachche ka naam upar aur side mein ho. Agar do log dost hain toh us square mein ✗ lagao. Kisi bhi pair ko check karna super fast hai — lekin un lakhon pairs ke liye bhi square waste hota hai jo dost nahi hain. Badi class = bahut bada grid. Method 2 (lists): har bachche ko ek sticky note do jisme sirf unke doston ke naam hon. Kam doston mein chhota hoga. Amy aur Ben dost hain ya nahi check karna ho toh Amy ki note padho — thoda slow hai, lekin koi space waste nahi. Kam dosti → sticky notes use karo (list). Sabko sabse jaanta ho → grid use karo (matrix).

Connections

Breadth-First Search (BFS) — $O (V + E)$ mein run karta hai kyunki yeh adjacency lists use karta hai.
Depth-First Search (DFS) — wahi $O (V + E)$ traversal bound.
Floyd-Warshall Algorithm — adjacency matrix prefer karta hai ( $O (1)$ edge weight access).
Dijkstra's Algorithm — sparse graphs ke liye adjacency list + priority queue.
Big-O Notation — yahan use ki gayi space/time trade-off vocabulary.
Sparse vs Dense Graphs — woh property jo choice decide karti hai.
Matrix Multiplication — explain karta hai $(A^{k})$ walks kaise count karta hai.