02
BFS and DFS Interactive Playground
Chapter 2 • Intermediate
120 min
BFS and DFS Interactive Playground
Breadth-First Search (BFS)
BFS explores level by level, visiting all neighbors before moving to next level.
Algorithm
- Start from source vertex
- Visit all neighbors at current level
- Move to next level
- Use queue to maintain order
Implementation
python.js
from collections import deque
def bfs(graph, start):
"""
BFS traversal of graph.
Time: O(V + E), Space: O(V)
"""
visited = [False] * len(graph)
queue = deque([start])
visited[start] = True
result = []
while queue:
vertex = queue.popleft()
result.append(vertex)
for neighbor in graph[vertex]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return result
Applications
- Shortest path in unweighted graphs
- Level-order traversal of trees
- Social network analysis (degrees of separation)
- Web crawling
- Broadcasting in networks
Shortest Path with BFS
python.js
def bfs_shortest_path(graph, start, end):
"""Find shortest path using BFS"""
if start == end:
return [start]
visited = [False] * len(graph)
parent = [-1] * len(graph)
queue = deque([start])
visited[start] = True
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if not visited[neighbor]:
visited[neighbor] = True
parent[neighbor] = vertex
queue.append(neighbor)
if neighbor == end:
# Reconstruct path
path = []
current = end
while current != -1:
path.append(current)
current = parent[current]
return path[::-1]
return None # No path exists
Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking.
Recursive Implementation
python.js
def dfs_recursive(graph, start, visited=None, result=None):
"""
DFS traversal using recursion.
Time: O(V + E), Space: O(V) for recursion stack
"""
if visited is None:
visited = [False] * len(graph)
if result is None:
result = []
visited[start] = True
result.append(start)
for neighbor in graph[start]:
if not visited[neighbor]:
dfs_recursive(graph, neighbor, visited, result)
return result
Iterative Implementation
python.js
def dfs_iterative(graph, start):
"""
DFS traversal using stack.
Time: O(V + E), Space: O(V)
"""
visited = [False] * len(graph)
stack = [start]
result = []
while stack:
vertex = stack.pop()
if not visited[vertex]:
visited[vertex] = True
result.append(vertex)
# Push neighbors in reverse order for same order as recursive
for neighbor in reversed(graph[vertex]):
if not visited[neighbor]:
stack.append(neighbor)
return result
Applications
- Topological sorting
- Detecting cycles
- Finding connected components
- Maze solving
- Path finding (not necessarily shortest)
Comparison
| Feature | BFS | DFS |
|---|---|---|
| Data Structure | Queue | Stack |
| Order | Level-order | Depth-order |
| Shortest Path | Yes (unweighted) | No |
| Space (worst) | O(V) | O(V) |
| Time | O(V + E) | O(V + E) |
| Use Case | Shortest path, level-order | Topological sort, cycles |
Cycle Detection
Using DFS
python.js
def has_cycle_dfs(graph):
"""Detect cycle in undirected graph using DFS"""
visited = [False] * len(graph)
def dfs(u, parent):
visited[u] = True
for v in graph[u]:
if not visited[v]:
if dfs(v, u):
return True
elif v != parent:
return True
return False
for i in range(len(graph)):
if not visited[i]:
if dfs(i, -1):
return True
return False
Connected Components
python.js
def connected_components(graph):
"""Find all connected components using DFS"""
visited = [False] * len(graph)
components = []
def dfs(u, component):
visited[u] = True
component.append(u)
for v in graph[u]:
if not visited[v]:
dfs(v, component)
for i in range(len(graph)):
if not visited[i]:
component = []
dfs(i, component)
components.append(component)
return components
Practice Problems
- Implement BFS and DFS for both directed and undirected graphs
- Find shortest path between two nodes using BFS
- Detect cycles in directed and undirected graphs
- Count connected components
- Find all paths between two nodes
- Level-order traversal of tree using BFS