title: "BFS & DFS: Graph Search Algorithms" description: "Implement BFS and DFS, understand maze solving, web crawling, social networks." order: 2
BFS & DFS: Graph Search Algorithms
Graph search is the foundation of pathfinding. Before learning A*, we must master two basic search algorithms:
- BFS (Breadth-First Search): Explores layer by layer, guarantees shortest path in unweighted graphs
- DFS (Depth-First Search): Goes deep first, then backtracks to explore other branches
BFS: Breadth-First Search
BFS is like dropping a stone in water - ripples expand outward layer by layer.
How BFS Works
1. Start from the starting node, mark as visited
2. Add start node to a Queue (FIFO)
3. While queue is not empty:
a. Dequeue the front element
b. Visit all unvisited neighbors of that element
c. Mark neighbors as visited and add them to the queue
4. Repeat until goal is found or queue becomes empty
BFS Implementation
from collections import deque
def bfs(graph, start, goal=None):
"""
Breadth-First Search
graph: adjacency list {node: [neighbors]}
start: starting node
goal: target node (if None, visits all)
"""
visited = set()
queue = deque([start])
visited.add(start)
parent = {start: None} # for path reconstruction
while queue:
node = queue.popleft()
print(f"Visiting: {node}", end=" -> " if node != goal else "\n")
if node == goal:
print(f"Found goal {goal}!")
path = []
while node is not None:
path.append(node)
node = parent[node]
return list(reversed(path))
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = node
queue.append(neighbor)
return None # goal not reachable
# Test graph: adjacency list
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E", "G"],
"G": ["F"]
}
path = bfs(graph, "A", "G")
print(f"BFS shortest path: {" -> ".join(path)}")
BFS Applications
- Maze solving: Guarantees finding the shortest exit path
- Social network "degrees of separation": LinkedIn shows 1st, 2nd, 3rd degree connections
- Network broadcasting: P2P networks propagate data efficiently
- Garbage Collection: Java and Python mark-and-sweep algorithm uses BFS
- Web crawling: Search engines prioritize nearby pages
DFS: Depth-First Search
DFS is like exploring a maze by always keeping your right hand on the wall - you go as deep as possible, then backtrack.
How DFS Works
1. Start from the starting node, mark as visited
2. Push start node onto a Stack (LIFO)
3. While stack is not empty:
a. Pop the top element
b. If it has unvisited neighbors, pick one and push it
c. If no unvisited neighbors, backtrack (pop the stack)
4. Repeat until goal is found or all nodes visited
DFS Implementation
def dfs(graph, start, goal=None):
"""
Depth-First Search
graph: adjacency list {node: [neighbors]}
start: starting node
goal: target node
"""
visited = set()
stack = [start]
parent = {start: None}
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(f"Visiting: {node}")
if node == goal:
path = []
while node is not None:
path.append(node)
node = parent[node]
return list(reversed(path))
# Reverse to visit in original order
for neighbor in reversed(graph.get(node, [])):
if neighbor not in visited:
parent[neighbor] = node
stack.append(neighbor)
return None
path = dfs(graph, "A", "G")
print(f"DFS found path: {" -> ".join(path)}")
DFS Applications
- Topological sorting: Determines compilation order in build systems
- Connected components: Image segmentation, community detection
- Maze generation: Randomized DFS (recursive backtracker) is the classic algorithm
- Abstract Syntax Tree traversal: Compilers walk AST with DFS
- Cycle detection: Detect cycles in directed graphs
BFS vs DFS Comparison
| Feature | BFS | DFS | |---------|-----|-----| | Data structure | Queue (FIFO) | Stack (LIFO) | | Shortest path | Guaranteed (unweighted) | Not guaranteed | | Memory usage | O(width), may be large | O(depth), usually smaller | | Completeness | Always finds solution | Always (finite graph) | | Optimality | Yes (unweighted) | No | | Best for | Finding shortest solution | Exploring all possibilities |
Hands-On: Maze Generation & Solving
Generate Maze with Randomized DFS
import random
from collections import deque
def generate_maze(width, height):
"""Generate maze using randomized DFS (recursive backtracker)"""
# Initialize: 1 = wall, 0 = passage
maze = [[1] * (2 * width + 1) for _ in range(2 * height + 1)]
start = (0, 0)
visited = set()
stack = [start]
visited.add(start)
maze[1][1] = 0 # Start cell
while stack:
x, y = stack[-1]
# Find unvisited neighbors
neighbors = []
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < width and 0 <= ny < height and (nx, ny) not in visited:
neighbors.append((nx, ny, dx, dy))
if neighbors:
nx, ny, dx, dy = random.choice(neighbors)
visited.add((nx, ny))
# Remove wall between current and new cell
maze[2 * y + 1 + dy][2 * x + 1 + dx] = 0
maze[2 * ny + 1][2 * nx + 1] = 0
stack.append((nx, ny))
else:
stack.pop()
return maze
def print_maze(maze):
"""Print maze with unicode block characters"""
for row in maze:
print("".join("โโ" if c else " " for c in row))
width, height = 10, 10
maze = generate_maze(width, height)
print("=== Generated Maze (10x10) ===")
print_maze(maze)
Solve Maze with BFS
def solve_maze_bfs(maze):
"""Solve maze using BFS, returns shortest path"""
height = len(maze)
width = len(maze[0])
start = (1, 1)
goal = (width - 2, height - 2)
queue = deque([start])
visited = {start}
parent = {start: None}
while queue:
x, y = queue.popleft()
if (x, y) == goal:
path = []
while (x, y) is not None:
path.append((x, y))
(x, y) = parent[(x, y)]
return list(reversed(path))
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx, ny = x + dx, y + dy
neighbor = (nx, ny)
if (0 <= nx < width and 0 <= ny < height
and maze[ny][nx] == 0
and neighbor not in visited):
visited.add(neighbor)
parent[neighbor] = (x, y)
queue.append(neighbor)
return None # No path found
path = solve_maze_bfs(maze)
if path:
print(f"\nBFS found shortest path: {len(path)} steps")
else:
print("No exit found!")
Decision Guide: When to Use Which?
Need shortest path (by edge count)?
Yes -> BFS (guarantees minimum edges)
No -> Consider:
Memory constrained? -> DFS (stack usually smaller)
Topological sorting? -> DFS (post-order traversal)
Explore all paths? -> DFS (backtracking)
Maze solving? -> BFS (shortest exit)
Memory Comparison
| Graph Structure | BFS Queue Size | DFS Stack Size | |:---------------|:--------------:|:--------------:| | Wide tree (100 branches) | ~100 | Tree height | | Deep tree (10,000 depth) | Widest level | ~10,000 | | Dense graph | Approaches V | At most V |
Generally: if branching factor is large, DFS uses less memory. If graph is very deep, BFS uses less memory.
Next Chapter: Dijkstra Algorithm
BFS only works when all edges have the same weight. Dijkstra extends to weighted graphs - it is the foundation of Google Maps and GPS navigation systems.