DFS

Depth-first search for cycle detection, topological ordering, and connectivity.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

DFS Basics

DFS explores as deep as possible before backtracking. Uses stack (recursion or explicit). Three states: unvisited (0), visiting (1), visited (2).

Godfs-traversal.go

21 linesLn 1, Col 1Go

Recursive DFS marks visited on entry. Processes all reachable nodes. Stack depth = O(V).

In directed graph: cycle if we encounter a node in 'visiting' state (gray). In undirected: cycle if neighbor is visited and not parent.

Gocycle-detection-in-directed-graph.go

38 linesLn 1, Col 1Go

White=unvisited, Gray=in recursion stack, Black=done. Gray→Gray edge = back edge = cycle. Works for disconnected graphs.

Linear ordering of DAG vertices where all edges go forward. DFS post-order reversed. Or Kahn's algorithm (BFS with indegree).

Gotopological-sort-(dfs).go

30 linesLn 1, Col 1Go

DFS post-order: add node after visiting all descendants. Reverse gives valid topological order. Only works for DAG (no cycles).

Run DFS/BFS from each unvisited node. Each traversal marks one component. Component ID array tracks which component each node belongs to.

Goconnected-components.go

26 linesLn 1, Col 1Go

Each unvisited node starts new component. DFS/BFS marks all reachable. comp[v] identifies component. O(V+E).

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.