Graph Traversal, Cycle Detection and Topological Sort

Learning Outcome

Pick DFS, BFS, Kahn's algorithm, or Euler-style DFS based on reachability, cycles, and ordering constraints.

Pattern Recognition

Item	Detail
Core signal	The problem contains dependencies, prerequisites, directed edges, components, or must-use-all-edges requirements.
Use when	Graph structure is explicit or can be built from relationships in the input.
Avoid when	The required invariant is not monotonic or the input constraints point to a simpler direct scan.

Intuition

Traversal answers reachability; topological sort answers dependency order; DFS path state detects directed cycles.

Exact Practice Question Names

Course Schedule
Course Schedule II
Find All Possible Recipes from Given Supplies
Largest Color Value in a Directed Graph
Reconstruct Itinerary
Strongly Connected Components

Interview Approach

Build adjacency lists carefully.
Use parent check for undirected cycles.
Use pathVis or indegree for directed cycles.
Use min-heap/multiset when lexical order matters.
For SCC, use Kosaraju or Tarjan after basic DFS is solid.

Pseudocode

build graph and indegree
queue = nodes with indegree 0
while queue not empty:
  node = pop
  order.add(node)
  for nei in graph[node]:
    indegree[nei] -= 1
    if indegree[nei] == 0: push nei
if order size != n: cycle exists

Sample Dry Run

For Course Schedule, courses with no prerequisites enter the queue first. If a cycle remains, some indegrees never become zero.

Edge Cases

Disconnected graph
Self-loop
Duplicate edges
Lexicographic tie-breaking

Common Mistakes

Using undirected cycle logic for directed graphs
Forgetting disconnected components
Not consuming all edges in itinerary

Complexity

Item	Detail
Expected time	O(V + E), plus sorting cost if adjacency order matters.
Expected space	O(V + E).

Java, C++ and Python Notes

Java: prefer explicit classes and clear helper methods over clever one-liners.
C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

Name the pattern before coding.
State the invariant or DP state in one sentence.
Dry-run the smallest non-trivial example.
Close with time and space complexity.