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.