Algorithm Guidecomplexity: O(V+E)

Depth-First Search (DFS)

A graph traversal that uses a LIFO stack to dive as deep as possible along one path, backtracking when it hits a dead end. It uses little memory (O(h)) and is central to cycle detection, topological sorting, and backtracking-based problem solving.

01Depth-First Search (DFS)

Explore How It Works

Starting DFS. Using a LIFO stack, dive as deep as possible along one path, then backtrack when stuck to try the next. The target is H.

Pop A and expand it. Push neighbors B, C onto the stack — C, pushed last, comes out next.

Pop C. Since C ≠ H, push neighbors F, G onto the stack. Descend deep into the right subtree.

Pop G. It's a leaf node with no neighbors to add, so we must backtrack. Pop the next node off the stack.

Pop F. Since F ≠ H, push neighbor H (C is already visited, so skip it).

Pop H. It matches the target — DFS reached it via A → C → F → H (depth 3).

Search complete · path A → C → F → H (cost 3). Light on memory at O(h), and the basis for cycle detection and backtracking.

Live Python

1def dfs(graph, start, target):

# stack = [A]

2 stack = [start]

3 visited = set()

4 parent = {start: None}

5 while stack:

6 current = stack.pop()

7 if current in visited:

8 continue

9 if current == target:

10 return reconstruct(parent, target)

11 visited.add(current)

12 for nb in graph[current]:

13 if nb not in visited:

14 parent[nb] = current

15 stack.append(nb)

16 return None

1 / 7

02 Understand It Simply

For Everyone

🔑How It Works

Follows one branch as far as it goes and returns to the last junction when it cannot continue.

💡In Plain Words

Explores one path as deep as possible with a stack, backtracking when stuck.

Uses little memory.

📍Where It's Used

–Cycle detection
–topological sorting
–backtracking problems

03 Python Implementation

A clean, readable reference implementation of the core logic of Depth-First Search (DFS).

core_implementation.py

def dfs(graph, start, target):
    stack = [start]
    visited = set()
    parent = {start: None}
    while stack:
        current = stack.pop()
        if current in visited:
            continue
        if current == target:
            return reconstruct(parent, target)
        visited.add(current)
        for nb in graph[current]:
            if nb not in visited:
                parent[nb] = current
                stack.append(nb)
    return None