21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

1. **Adjacency Matrix ($V \times V$ 2D Array):** $O(V^2)$ Space. Dense graphs ke liye best.
2. **Adjacency List (`dict[int, list[int]]`):** $O(V + E)$ Space (Industry Standard!).

```python
from collections import defaultdict

# Building an undirected graph from edge list:
edges = [[0, 1], [0, 2], [1, 2], [2, 3]]
graph = defaultdict(list)

for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
```

---

### 2. Graph DFS Traversal (Recursion / Visited Set)

```python
def dfs(node: int, graph: dict, visited: set):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited)
```

---

### 3. Graph BFS Traversal (Shortest Path in Unweighted Graph)

```python
from collections import deque

def bfs_shortest_path(start: int, target: int, graph: dict) -> int:
    queue = deque([(start, 0)]) # (node, distance)
    visited = {start}
    
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
            
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
                
    return -1
```

---

### 4. Master Comparison Matrix

| Feature | Adjacency Matrix | Adjacency List |
| :--- | :--- | :--- |
| **Space Complexity** | $O(V^2)$ (Heavy for sparse graphs) | ⚡ **$O(V + E)$ (Optimal)** |
| **Check if $(u, v)$ has Edge**| ⚡ **$O(1)$ (`matrix[u][v] == 1`)** | $O(\text{deg}(u))$ |
| **Iterate all neighbors of $u$**| $O(V)$ | ⚡ **$O(\text{deg}(u))$** |

---

### 5. Interview Ke 3 Sawal Is Topic Se

1. **Connected Components count graph me kaise find karte hain?** -> Loop from $0$ to $V-1$; agar node visited nahi hai toh `count += 1` karke DFS/BFS trigger karo.
2. **Bipartite Graph (Graph Coloring) kya hoti hai?** -> Aisi graph jiske saare nodes ko 2 colors me divide kiya ja sake jisme koi bhi do adjacent nodes ka color same na ho (No odd-length cycles).
3. **Graph me BFS hamesha unweighted shortest path kyu deta hai?** -> Kyunki BFS saari directions me uniform 1-step radius expand karta hai, isliye pehli baar target reach hone par wahi minimum step count hota hai.

---
**Next Topic:** 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph

Loading lesson content...

JavaScript

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track