Dfs Vs Bfs

Choose between DFS and BFS for graph traversal problems. Use when deciding whether to explore depth-first (cycle detection, paths) or breadth-first (shortest path, levels).

knoopx 5c50b44 980 B Updated

File contents

When to use

DFS (stack/recursion) explores one branch fully before backtracking. BFS (queue) explores level-by-level.

Rules

  • If the problem asks "shortest" or "minimum steps" on an unweighted graph, ALWAYS choose BFS
  • If it asks "all paths," "can we reach," or "count islands," DFS is simpler
  • NEVER use BFS for cycle detection — DFS is the right tool
  • Both visit each node once: O(V+E) time

DFS use cases

Cycle detection, topological sort, path existence, connected components, backtracking puzzles, flood fill.

BFS use cases

Shortest unweighted path, level-order traversal, nearest neighbor, minimum steps.

Example

"Count islands" → DFS flood-fill on 2D grid. "Shortest path in maze" → BFS with queue tracking (row, col, distance).

knoopx/pi/tree/main/agent/skills/knowledge/dfs-vs-bfs commit 5c50b44c08

Frequently asked questions

npx skillmds@latest add knoopx/dfs-vs-bfs