graph-traversal-patterns

Use BFS for unweighted shortest paths with no exceptions, since it explores nodes in order of distance from the source. DFS finds the first path it encounters, which passes small tests but is not guaranteed to be the shortest.

Use three-color DFS (white/gray/black): a gray-to-gray edge indicates a cycle. A two-state visited set gives false positives on diamond shapes where two paths converge on the same node without forming a cycle.

Use union-find when connectivity queries interleave with incremental edge additions, since path compression and union by size make each operation effectively O(1). Re-running BFS per query degrades to accidental O(VE) on streaming merges.

The cause is marking nodes as visited when popped instead of when enqueued. Mark-on-pop lets the same node enter the queue once per incoming edge, causing exponential queue growth; mark nodes at enqueue time.

No, BFS only handles unweighted graphs. For weighted edges, escalate to Dijkstra for positive weights, 0-1 BFS for 0/1 weights, or Bellman-Ford when negative weights are present.

Run Kahn's algorithm and check the leftover nodes with indegree greater than zero after processing — they contain the cycle. This also gives a loud failure instead of the plausible wrong order that DFS post-order toposort produces on cyclic input.