A
AiTechWorlds
AiTechWorlds
You've just arrived in an unfamiliar city with a map and a starting point: your hotel. You want to explore every street and district.
Strategy A — The Systematic Explorer (BFS): On Day 1, you visit every block directly connected to your hotel. On Day 2, you visit every block connected to those, and so on — expanding outward like ripples in a pond. You always fully explore your current "ring" before moving further out. This is Breadth-First Search.
Strategy B — The Adventurer (DFS): You pick one street, walk as far as it goes — into the old quarter, through the market, deeper into the maze of alleys — until you hit a dead end. Then you backtrack and try the next unexplored turning. This is Depth-First Search.
Neither approach is universally better. They answer different questions. BFS tells you the shortest path to any location. DFS tells you whether any path exists and is better for exploring structure.
Both algorithms operate on graphs — a collection of nodes (vertices) connected by edges.
Example Graph:
A --- B --- E
| |
C --- D --- F
As an adjacency list (the most common representation):
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'D'],
'D': ['B', 'C', 'F'],
'E': ['B'],
'F': ['D']
}
BFS uses a queue (FIFO — First In, First Out). It processes nodes level by level:
BFS from A:
Level 0: [A]
Level 1: [B, C] (A's neighbors)
Level 2: [D, E] (B's and C's unvisited neighbors)
Level 3: [F] (D's unvisited neighbor)
from collections import deque
def bfs(graph, start):
visited = set() # Track visited nodes to avoid cycles
queue = deque([start]) # Initialize queue with start node
visited.add(start)
traversal_order = []
while queue: # Continue until queue is empty
node = queue.popleft() # Dequeue from the FRONT (FIFO)
traversal_order.append(node)
print(f"Visiting: {node}")
for neighbor in graph[node]: # Examine all neighbors
if neighbor not in visited:
visited.add(neighbor) # Mark visited BEFORE enqueuing
queue.append(neighbor) # Add to the BACK of the queue
return traversal_order
# --- Example ---
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'D'],
'D': ['B', 'C', 'F'],
'E': ['B'],
'F': ['D']
}
print("BFS traversal from A:")
order = bfs(graph, 'A')
print(f"Order visited: {order}")
Output:
BFS traversal from A:
Visiting: A
Visiting: B
Visiting: C
Visiting: D
Visiting: E
Visiting: F
Order visited: ['A', 'B', 'C', 'D', 'E', 'F']
BFS guarantees the shortest path in an unweighted graph because it explores all nodes at distance d before any node at distance d+1.
def bfs_shortest_path(graph, start, end):
if start == end:
return [start]
visited = {start}
queue = deque([[start]]) # Queue stores entire PATHS, not just nodes
while queue:
path = queue.popleft() # Current path being explored
node = path[-1] # Last node in path
for neighbor in graph[node]:
if neighbor not in visited:
new_path = path + [neighbor]
if neighbor == end: # Found the destination
return new_path
visited.add(neighbor)
queue.append(new_path)
return None # No path exists
# --- Example ---
path = bfs_shortest_path(graph, 'A', 'F')
print(f"Shortest path from A to F: {path}")
Output:
Shortest path from A to F: ['A', 'B', 'D', 'F']
DFS uses a stack (LIFO — Last In, First Out). It dives as deep as possible before backtracking:
DFS from A (recursive flavor):
Visit A → Visit B → Visit D → Visit C (already visited A)
→ Visit F → backtrack
→ backtrack to D → backtrack to B
→ Visit E → backtrack
→ backtrack to A
→ Visit C (A's other neighbor)
def dfs_recursive(graph, node, visited=None, order=None):
if visited is None:
visited = set()
if order is None:
order = []
visited.add(node) # Mark current node as visited
order.append(node)
print(f"Visiting: {node}")
for neighbor in graph[node]: # Explore each neighbor
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited, order) # Recurse deeper
return order
# --- Example ---
print("\nDFS (recursive) from A:")
order = dfs_recursive(graph, 'A')
print(f"Order visited: {order}")
Output:
DFS (recursive) from A:
Visiting: A
Visiting: B
Visiting: D
Visiting: C
Visiting: F
Visiting: E
Order visited: ['A', 'B', 'D', 'C', 'F', 'E']
def dfs_iterative(graph, start):
visited = set()
stack = [start] # Use list as stack
order = []
while stack:
node = stack.pop() # Pop from the TOP (LIFO)
if node not in visited:
visited.add(node)
order.append(node)
print(f"Visiting: {node}")
# Push neighbors (in reverse order to maintain consistent traversal)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return order
# --- Example ---
print("\nDFS (iterative) from A:")
order = dfs_iterative(graph, 'A')
print(f"Order visited: {order}")
Output:
DFS (iterative) from A:
Visiting: A
Visiting: B
Visiting: D
Visiting: C
Visiting: F
Visiting: E
Order visited: ['A', 'B', 'D', 'C', 'F', 'E']
Same graph, same starting point. Notice how differently they traverse:
Graph: BFS Order: DFS Order:
A --- B A (start) A (start)
| | B (level 1) B (go deep)
C --- D C (level 1) D (deeper)
| D (level 2) C (D's neighbor)
E E (level 2) E (C's unvisited)
BFS explores by proximity. DFS explores by depth.
Good for: shortest path Good for: connectivity, structure
BFS Applications:
DFS Applications:
| Property | BFS | DFS |
|---|---|---|
| Time complexity | O(V + E) | O(V + E) |
| Space complexity | O(V) — queue can hold all nodes | O(V) — recursion stack or explicit stack |
| Complete | Yes (finds all reachable nodes) | Yes (finds all reachable nodes) |
| Optimal path | Yes (unweighted shortest path) | No |
| Memory usage | Higher (stores entire frontier) | Lower (stores single path) |
| Handles cycles | Yes (with visited set) | Yes (with visited set) |
V = number of vertices, E = number of edges
| Scenario | Use | Reason |
|---|---|---|
| Shortest path (unweighted) | BFS | Guarantees minimum hops |
| Find if path exists | Either | Both work |
| Explore all connected nodes | Either | Both are complete |
| Detect cycles | DFS | Natural with recursion stack |
| Topological sort | DFS | Post-order naturally gives topo order |
| Social network distance | BFS | Finds minimum connections |
| Solve a maze | DFS | Explores one path fully before backtracking |
| Level-by-level processing | BFS | Built-in level structure |
| Memory constrained, deep graph | DFS | Queue in BFS can get very large |
| Wide shallow graph | BFS | Stack in DFS stays small |
Graph traversal problems are among the most common in technical interviews. The key is recognizing which traversal a problem is really asking for:
Once you recognize BFS and DFS as fundamental patterns — not just code to memorize — you can construct solutions to novel graph problems on the fly.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises