TraversalO(V + E)· Level 02

Depth-First Search (DFS)

Dive deep, then backtrack — basis for topo sort & SCC.

Intuition

DFS is the explorer who walks down a corridor as far as it goes before turning back. Implemented with a stack (or recursion), it produces a tree of discovery times that unlocks topological sorting, cycle detection, and strongly connected components.

Step-by-step

1
Mark the start vertex as visited and record its discovery time.
2
For each unvisited neighbor, recursively call DFS on it.
3
After all neighbors are exhausted, record the finish time.
4
Use discovery/finish times to detect back edges (cycles) and topological order.

Pseudocode

pseudocode

DFS(G):
  for each v in V: visited[v] = false
  for each v in V:
    if not visited[v]:
      DFS_VISIT(G, v)

DFS_VISIT(G, u):
  visited[u] = true
  for v in G.neighbors(u):
    if not visited[v]:
      parent[v] = u
      DFS_VISIT(G, v)

Implementation (Python)

python

def dfs(graph, start):
    visited = set()
    order = []

    def visit(u):
        visited.add(u)
        order.append(u)
        for v, _ in graph.neighbors(u):
            if v not in visited:
                visit(v)

    visit(start)
    return order

Real-world applications

Topological sorting of build dependencies
Detecting cycles in directed graphs
Finding strongly connected components (Tarjan, Kosaraju)
Maze solving and backtracking