DFS & BFS
DFS explores as deep as possible before backtracking (uses stack/recursion); BFS explores all neighbors at the current depth before going deeper (uses queue).
DFS = a curious cat going down every hallway until it hits a dead end, then backing up. BFS = a ripple in a pond -- expands evenly in all directions, reaching the nearest shore first.
BFS guarantees shortest path in unweighted graphs — DFS does not. DFS uses O(depth) space (call stack); BFS uses O(width) space (queue). DFS with a visited set detects cycles in directed graphs. BFS level-by-level traversal is useful for 'minimum steps' problems. For trees (no cycles), DFS is often more natural; for graphs, always track visited to avoid infinite loops.
Iterative DFS uses an explicit stack and reverses the children order to match recursive traversal order. BFS on a weighted graph is wrong for shortest path — you need Dijkstra. For bidirectional BFS, run BFS from both source and target simultaneously — reduces search space from O(b^d) to O(b^(d/2)) where b is branching factor. Topological sort is DFS where you add nodes to the front of the result after visiting all descendants. Kosaraju's algorithm for strongly connected components (SCCs) does two DFS passes — first on original graph, second on reversed graph in reverse finish-time order.
My decision between DFS and BFS: if the problem asks for shortest path (unweighted), use BFS. If the problem asks for existence, connected components, cycle detection, or topological order, DFS is usually simpler. For trees specifically, DFS maps to recursive thinking — define the return value per node and let the recursion compose. For graphs, I always maintain a visited set. I also consider space: BFS can be memory-heavy if the graph is wide, DFS can stack-overflow if the graph is deep.
BFS finds the shortest path in UNWEIGHTED graphs only. If edges have different weights, BFS gives wrong shortest paths — use Dijkstra. Also: DFS on a graph without a visited set will loop forever on cycles. Forgetting 'visited' for graph DFS is the #1 mistake.