Graph Traversal: BFS, DFS, Adjacency List vs. Matrix (Ultimate Guide 2025)
This in-depth article explores graph traversals—Breadth First Search (BFS), Depth First Search (DFS), and compares the adjacency list versus adjacency matrix representations. With real code, diagrams, SEO-optimized content, and practical Q&A, it’s your all-in-one resource for interviews & development.
Table of Contents
- Introduction to Graphs
- Graph Representations (Adjacency List vs. Matrix)
- Breadth First Search (BFS)
- Depth First Search (DFS)
- Adjacency List vs. Matrix: Full Comparison
- Common Interview Problems
- FAQ & Best Practices
Introduction to Graphs
A graph is a data structure made up of nodes (vertices) connected by edges. Graphs can model anything from social networks to road maps, the web, or biological pathways[8].
- Vertex (Node): An entity or point (denoted as
V) - Edge (Link): A connection between two vertices (denoted as
E)
Graphs are classified as:
- Directed (edges have direction) or Undirected
- Weighted (edges carry a cost) or Unweighted
- Sparse (few edges), Dense (many edges)
Graph Representations: Adjacency List vs. Matrix
The two most common ways to represent a graph are the adjacency list and the adjacency matrix[19][7][11]. Choosing the right one is crucial for performance and memory efficiency.
Adjacency List
- Each node stores a list of its adjacent nodes (its direct neighbors).
- Efficient for sparse graphs (few edges).
- Space: O(V+E) where V is vertices, E is edges.
Adjacency List of Graph: 0: 1, 2 1: 0, 2, 3 2: 0, 1, 4 3: 1, 4 4: 2, 3
Adjacency Matrix
- A 2D array (VxV) where cell [i][j] is 1 if edge exists, 0 otherwise.
- Efficient for dense graphs (many edges).
- Space: O(V2)
Adjacency Matrix of above graph: 0 1 2 3 4 0 [0 1 1 0 0] 1 [1 0 1 1 0] 2 [1 1 0 0 1] 3 [0 1 0 0 1] 4 [0 0 1 1 0]
Pros and Cons Table
| Aspect | Adjacency List | Adjacency Matrix |
|---|---|---|
| Best for | Sparse graphs | Dense graphs |
| Space Complexity | O(V+E)[7][19][11] | O(V2)[7][19][11] |
| Edge Lookup | O(k) (k: neighbors) | O(1)[7][19][11] |
| Add/Remove Edge | O(1) avg. | O(1) |
| Add Vertex | O(1)[7] | O(V2)[7] |
Breadth First Search (BFS) Explained
BFS (Breadth First Search) is a classic graph traversal algorithm. It explores neighbors first before moving deeper[6][3].
- Uses: Shortest path in unweighted graphs, connected components, levels in trees, etc.
- Method: Uses a queue data structure.
- Time Complexity: O(V+E) (adjacency list), O(V2) (matrix)[4][6]
BFS Algorithm (Step-by-Step)
- Start from a source node. Mark as visited.
- Enqueue all its unvisited neighbors.
- Visit nodes in queue order, repeating the process for each dequeued node.
# BFS in Python using Adjacency List
from collections import deque
def bfs(adj, start):
visited = set([start])
q = deque([start])
while q:
node = q.popleft()
print(node, end=" ")
for neighbor in adj[node]:
if neighbor not in visited:
visited.add(neighbor)
q.append(neighbor)
# Example use
adj = {0:[1,2], 1:[0,2,3], 2:[0,1,4], 3:[1,4], 4:[2,3]}
bfs(adj, 0)
# Output: 0 1 2 3 4
Depth First Search (DFS) Explained
DFS (Depth First Search) explores as far as possible along each branch before backtracking[5][18]. It’s essential for connected components, topological sorting, cycle detection, and more.
- Method: Can use a stack (explicit) or recursion (implicit stack).
- Time Complexity: O(V+E) (adjacency list), O(V2) (matrix)
DFS Algorithm (Step-by-Step)
- Begin at source, mark as visited.
- Recursively explore or stack-push all unvisited neighbors before returning.
- Backtrack when no new neighbors are found.
# DFS in Python using Adjacency List
def dfs(adj, node, visited=None):
if visited is None:
visited = set()
print(node, end=" ")
visited.add(node)
for neighbor in adj[node]:
if neighbor not in visited:
dfs(adj, neighbor, visited)
# Example use
dfs(adj, 0)
# Output: 0 1 2 4 3
Adjacency List vs. Matrix: Which to Use?
Choosing between an adjacency list and a matrix hinges on your graph’s density, the algorithms you’ll run, and memory limits[15][19][11].
- Sparse Graph (few edges): Adjacency list better. Lower memory usage, faster neighbor iteration.
- Dense Graph (many edges): Adjacency matrix faster for edge lookups, but uses more memory.
- Edge existence queries: Matrices lookup in O(1); lists in O(k) (k=neighbors).
- Adding/removing vertices: Easier with lists; matrices are rigid, especially for dynamic graphs[7][11].
| Scenario | Best Representation | Reason |
|---|---|---|
| Social networks, sparse data | Adjacency List | Saves space, quick to iterate friends[15] |
| Network routing, dense graphs | Adjacency Matrix | Instant edge checks, despite heavy memory |
Common Interview Problems: BFS and DFS Patterns
- Find shortest path in an unweighted graph (BFS)
- Detect cycles in a graph (DFS)
- Count connected components (DFS/BFS)
- Level order traversal of a tree (BFS)
- Topological sorting (DFS)
Practice Problem: Number of Islands (LeetCode 200)
- Use BFS/DFS to explore all “connected” land squares.
- Mark visited; increment island count whenever new land is found.
def numIslands(grid):
if not grid: return 0
rows, cols = len(grid), len(grid[0])
visited = set()
islands = 0
def dfs(r, c):
if (r<0 or c<0 or r>=rows or c>=cols or grid[r][c]!='1' or (r,c) in visited): return
visited.add((r,c))
for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
dfs(r+dr, c+dc)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1' and (r,c) not in visited:
dfs(r,c)
islands += 1
return islands
FAQ & Best Practices
Is adjacency list always better?
No—if the graph is dense, an adjacency matrix may be faster for edge lookups and can outperform a list.
Do BFS and DFS always find the same paths?
No—BFS gives the shortest path (in unweighted graphs), DFS may not[3][14].
When should I use a matrix?
For dense graphs, or when you need constant-time edge existence checks. Useful in network flows and connectivity-wise complete networks.
Can you run BFS/DFS with either representation?
Yes. Both adjacency list and matrix can be used, though lists are almost always faster except in some dense use cases[4][15].
Is recursion required for DFS?
No—you can implement DFS with an explicit stack instead of recursion to prevent stack overflow on very large graphs.
Understanding BFS, DFS, and graph representations is essential for both coding interviews and real-world programming. Pick adjacency lists for sparse graphs and adjacency matrices for dense graphs. BFS is best for shortest path problems; DFS excels in deep structure and connectivity analysis.
){kind=link}
0 Comments