Loading...
Graphs, traversal, and shortest paths
Section 2 of 4
Master DFS and BFS - the fundamental algorithms for exploring graphs
Explores as far as possible along each branch before backtracking.
Uses a stack (or recursion). Go deep first, then backtrack when stuck.
O(V + E) time, O(V) space for recursion stack
Explores all neighbors at the current depth before moving to the next level.
Uses a queue. Explore level by level, breadth first.
O(V + E) time, O(V) space for queue
function DFS(graph, start):
visited = set()
stack = [start]
while stack is not empty:
node = stack.pop()
if node not in visited:
visited.add(node)
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.push(neighbor)
// Recursive version
function DFS_Recursive(graph, node, visited):
visited.add(node)
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
DFS_Recursive(graph, neighbor, visited)function BFS(graph, start):
visited = set()
queue = [start]
visited.add(start)
while queue is not empty:
node = queue.dequeue()
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.enqueue(neighbor)
// Distance tracking version
function BFS_Distances(graph, start):
distances = {start: 0}
queue = [start]
while queue is not empty:
node = queue.dequeue()
for neighbor in graph[node]:
if neighbor not in distances:
distances[neighbor] = distances[node] + 1
queue.enqueue(neighbor)