Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

DFS / BFS

Visit every node and edge once with a visited set.

time O(V + E)space O(V)

What it is

Depth-first uses recursion or a stack; breadth-first uses a queue and finds shortest paths in unweighted graphs. With a visited set each node and edge is processed once: O(V + E).

When to reach for it

  • Connected components, flood fill
  • Shortest path in unweighted graph or grid
  • Cycle detection, topological order

Clues in the problem

  • Grid or adjacency list input
  • “Minimum steps” (BFS)
  • Explore all reachable states (DFS)

Template

from collections import deque
def bfs(graph, start):
seen, q = {start}, deque([start])
while q:
u = q.popleft()
for v in graph[u]:
if v not in seen:
seen.add(v) # mark when enqueued
q.append(v)
return seen

Practice problems

  • Number of Islands
  • Word Ladder
  • Course Schedule
  • Clone Graph

Common mistakes

  • Marking visited on dequeue, causing duplicate queue entries
  • Deep recursion overflow on large graphs
  • Forgetting disconnected components