Graphs are one of the most important DSA topics for interviews and exams.
A graph is a collection of:
- Vertices / Nodes
- Edges / Connections
Example:
1
/ \
2 3
| |
4---5
Here:
Nodes = {1, 2, 3, 4, 5}
Edges = {(1,2), (1,3), (2,4), (3,5), (4,5)}
1. Types of Graphs
Undirected Graph
Connection works both ways.
1 ---- 2
If 1 is connected to 2, then 2 is connected to 1.
Directed Graph
Edges have a direction.
1 ---> 2
This means:
1 → 2
but not necessarily:
2 → 1
Weighted Graph
Edges have costs/weights.
1 --5--> 2
The cost of travelling from 1 to 2 is 5.
Unweighted Graph
All edges are treated equally.
1 ---- 2
2. How to Represent a Graph
There are three common representations.
A. Adjacency Matrix
For:
1 ---- 2
| |
| |
3 ---- 4
We can use:
graph = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]
]
graph[i][j] == 1 means an edge exists.
Complexity
Space:
O(V²)
Useful when the graph has many edges.
3. Adjacency List
This is usually the most useful representation in interviews.
For:
1 ---- 2
| |
| |
3 ---- 4
We can write:
graph = {
1: [2, 3],
2: [1, 4],
3: [1, 4],
4: [2, 3]
}
Or more commonly with defaultdict:
from collections import defaultdict
graph = defaultdict(list)
graph[1].append(2)
graph[2].append(1)
Complexity
Space:
O(V + E)
This is usually preferred for sparse graphs.
4. Building an Undirected Graph
Suppose edges are:
edges = [
[0, 1],
[0, 2],
[1, 3],
[2, 3]
]
Build the adjacency list:
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
Result:
0 → [1, 2]
1 → [0, 3]
2 → [0, 3]
3 → [1, 2]
Important
For an undirected graph:
graph[u].append(v)
graph[v].append(u)
For a directed graph:
graph[u].append(v)
Only one direction is added.
5. Graph Traversal
The two fundamental graph traversal techniques are:
- DFS — Depth First Search
- BFS — Breadth First Search
You already learned BFS when studying trees. The same idea applies to graphs, but graphs require extra care because they can contain cycles.
6. DFS — Depth First Search
DFS goes as deep as possible before backtracking.
Example:
1
/ \
2 3
/ \
4 5
Possible DFS:
1 → 2 → 4 → 5 → 3
Recursive DFS
def dfs(graph, node, visited):
if node in visited:
return
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
Usage:
visited = set()
dfs(graph, 0, visited)
7. Why Do We Need visited?
Consider:
1 ---- 2
Since the graph is undirected:
1 → 2
2 → 1
Without visited, DFS could repeatedly do:
1 → 2 → 1 → 2 → 1 → ...
So:
visited = set()
is one of the most important graph patterns.
8. DFS Iteratively
Instead of recursion, use a stack.
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return visited
Remember:
DFS → Stack
BFS → Queue
9. BFS in a Graph
BFS explores nodes level by level.
Use:
from collections import deque
Template:
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Important interview detail
Mark a node visited when you add it to the queue, not when you remove it.
Good:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
This prevents duplicate queue entries.
10. Number of Connected Components
Suppose:
1 --- 2 4 --- 5
3
There are:
3 connected components
Solution
Run DFS from every unvisited node.
def count_components(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
for node in range(n):
if node not in visited:
count += 1
dfs(node)
return count
Pattern
For every unvisited node:
start DFS/BFS
count one component
11. Number of Islands 🌊
This is one of the most famous graph/grid interview questions.
Given:
1 1 0 0
1 0 0 1
0 0 1 1
Each group of connected 1s is an island.
Answer:
3
DFS solution
def num_islands(grid):
rows = len(grid)
cols = len(grid[0])
count = 0
def dfs(r, c):
if (
r < 0 or
r >= rows or
c < 0 or
c >= cols or
grid[r][c] != "1"
):
return
grid[r][c] = "0"
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
count += 1
dfs(r, c)
return count
Key pattern
Whenever you see:
connected cells / regions / islands
Think:
DFS or BFS
12. Graph Cycle Detection — Undirected Graph
Example:
1
| \
| \
2---3
This contains a cycle.
For an undirected graph, while doing DFS, keep track of the parent.
def has_cycle(graph, n):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True
return False
for node in range(n):
if node not in visited:
if dfs(node, -1):
return True
return False
Why neighbor != parent?
Suppose:
1 ---- 2
From 1, we visit 2.
From 2, we see 1 again.
That's not a cycle — it's simply the edge we came from.
13. Cycle Detection — Directed Graph
Directed graphs require a different technique.
We maintain:
visited
current recursion path
Example:
1 → 2 → 3
↑ |
└───┘
There is a directed cycle.
def has_cycle_directed(graph, n):
visited = set()
path = set()
def dfs(node):
if node in path:
return True
if node in visited:
return False
visited.add(node)
path.add(node)
for neighbor in graph[node]:
if dfs(neighbor):
return True
path.remove(node)
return False
for node in range(n):
if dfs(node):
return True
return False
The important distinction:
Undirected → parent tracking
Directed → recursion path / 3-state DFS
14. Shortest Path in an Unweighted Graph
This is a very important BFS application.
Suppose:
0 -- 1 -- 2 -- 3
|
4
To find the shortest number of edges from 0 to 3, use BFS.
from collections import deque
def shortest_path(graph, start, target):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == target:
return distance
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, distance + 1))
return -1
Why BFS?
Because BFS explores:
distance 0
distance 1
distance 2
distance 3
...
So the first time you reach the target, you've found a shortest path in an unweighted graph.
15. Shortest Path in a Grid
Suppose:
0 0 0
1 1 0
0 0 0
You can move:
↑ ↓ ← →
This is also a graph.
Each cell is effectively a node.
Neighbors are:
directions = [
(1, 0),
(-1, 0),
(0, 1),
(0, -1)
]
This pattern appears constantly in interviews.
16. Multi-Source BFS
Suppose several starting nodes spread simultaneously.
Example:
2 1 1
1 1 0
0 1 1
2 represents an already-processed source.
If multiple 2s exist, put all of them into the queue initially.
queue = deque()
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
Then perform normal BFS.
This is called:
Multi-source BFS
Classic example:
Rotting Oranges
17. Topological Sort
Topological sorting applies to a directed acyclic graph (DAG).
Suppose:
A → B
A → C
B → D
C → D
A valid ordering is:
A → B → C → D
The key requirement:
Every prerequisite must appear before the thing that depends on it.
This is useful for:
- Course prerequisites
- Task dependencies
- Build systems
- Scheduling
18. Topological Sort Using Kahn's Algorithm
Calculate the indegree of every node.
indegree = number of incoming edges
Nodes with:
indegree == 0
can be processed first.
from collections import deque
def topological_sort(n, edges):
graph = [[] for _ in range(n)]
indegree = [0] * n
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
queue = deque()
for i in range(n):
if indegree[i] == 0:
queue.append(i)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
if len(order) != n:
return []
return order
Important
If:
len(order) != n
then there is a cycle.
19. DFS vs BFS
| DFS | BFS |
|---|---|
| Stack / recursion | Queue |
| Goes deep first | Goes level by level |
| Connected components | Shortest unweighted path |
| Cycle detection | Level distances |
| Backtracking | Multi-source BFS |
| Topological sort | Topological sort |
20. Graph Complexity
With adjacency lists:
DFS
O(V + E)
BFS
O(V + E)
Why?
Every vertex and edge is processed a limited number of times.
Space:
O(V + E)
for the graph plus traversal structures.
21. Graph Problem Recognition 🧠
This is one of the most valuable things to memorize.
| Problem wording | Think |
|---|---|
| Visit all connected nodes | DFS/BFS |
| Connected components | DFS/BFS |
| Number of islands | DFS/BFS |
| Shortest unweighted path | BFS |
| Minimum number of moves | BFS |
| Spread simultaneously | Multi-source BFS |
| Prerequisites | Topological sort |
| Dependency ordering | Topological sort |
| Detect undirected cycle | DFS + parent |
| Detect directed cycle | DFS + recursion path |
| Weighted shortest path | Dijkstra |
| Negative edge weights | Bellman-Ford |
| Connect all nodes cheaply | MST |
| Minimum spanning tree | Kruskal / Prim |
22. The Most Important Graph Template
For an undirected graph:
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node):
if node in visited:
return
visited.add(node)
for neighbor in graph[node]:
dfs(neighbor)
Memorize this structure.
You can adapt it to many problems.
23. Grid DFS Template
Also memorize this:
def dfs(r, c):
if (
r < 0 or
r >= rows or
c < 0 or
c >= cols
):
return
if grid[r][c] == 0:
return
grid[r][c] = 0
for dr, dc in directions:
dfs(r + dr, c + dc)
Then:
directions = [
(1, 0),
(-1, 0),
(0, 1),
(0, -1)
]
This solves a huge family of grid problems.
24. What You Should Know for Exams
Make sure you can implement these without looking at notes:
Level 1
- Build adjacency list
- DFS
- BFS
- Detect connected components
- Number of islands
Level 2
- Shortest path using BFS
- Cycle detection
- Flood Fill
- Rotting Oranges
- Course Schedule
Level 3
- Topological Sort
- Dijkstra's Algorithm
- Union-Find / DSU
- Minimum Spanning Tree
- Kruskal's Algorithm
- Prim's Algorithm
⭐ Most Important Interview Questions
If you're prioritizing practice, focus on:
1. Number of Islands
2. Clone Graph
3. Rotting Oranges
4. Course Schedule
5. Course Schedule II
6. Pacific Atlantic Water Flow
7. Graph Valid Tree
8. Number of Connected Components
9. Word Ladder
10. Network Delay Time
The next major graph topic is Shortest Path Algorithms, where we'll learn Dijkstra's algorithm, 0-1 BFS, Bellman-Ford, and when to use each one.
Top comments (0)