Graph Search, Connectivity, And State-Space Algorithms

What's being tested

These problems test practical graph traversal and state-space search skills: reachability, shortest-path in unweighted graphs, and exploring implicit graphs where nodes are positions or states. Interviewers probe ability to choose BFS/DFS/Union-Find, encode state efficiently, and control complexity for spatial or implicit-edge graphs.

Patterns & templates

• BFS for unweighted shortest path and reachability — enqueue on discovery, O(V+E) time, O(V) space; avoid revisiting.
• DFS for reachability or full-exploration — recursion or explicit stack; watch recursion depth and mark visited on push.
• Union-Find (DSU) for offline connectivity queries — near O(α(N)) per op; use path compression + union by rank.
• Squared-distance check to avoid sqrt cost and floating errors: compare dx*dx + dy*dy <= r*r.
• Implicit graph generation: avoid building O(N^2) edges by spatial bucketing or KD-tree to find neighbors within threshold.
• State encoding as tuple/bitmask for multi-variable state (pos, cleaned-set) — use bitmask when dirty-count ≤ 20 for 2^k compactness.
• Visited set semantics: store full state when searching state-space (not just position) to prevent exponential re-exploration.

Common pitfalls

Pitfall: Building full adjacency for N ~10k causes O(N^2) time/memory; use spatial indexing or neighbor pruning.

Pitfall: Marking visited only on pop (instead of on push) creates duplicate queue entries and slows BFS substantially.

Pitfall: Comparing Euclidean distances with sqrt causes unnecessary floating error and CPU cost; use squared comparisons instead.