Recursive template

void dfs(Node cur, Set visited) {
  if (!visited.add(cur)) return;
  process(cur);
  for (Node next : cur.neighbors) dfs(next, visited);
}
Advertisement

Iterative with stack

Deque stack = new ArrayDeque<>();
Set visited = new HashSet<>();
stack.push(start);
while (!stack.isEmpty()) {
  Node cur = stack.pop();
  if (!visited.add(cur)) continue;
  process(cur);
  for (Node next : cur.neighbors)
    if (!visited.contains(next)) stack.push(next);
}
Advertisement

Applications

  • Topological sort
  • Cycle detection
  • Strongly connected components
  • Path finding

Discovery + finish times

Record when node discovered + finished. Enables SCC (Tarjan, Kosaraju) and topological sort.