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

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

1. Build adjacency lists carefully.
2. Use parent check for undirected cycles.
3. Use pathVis or indegree for directed cycles.
4. Use min-heap/multiset when lexical order matters.
5. 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

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.