Depth-First Search

Depth-First Search (DFS)

DFS explores a graph by going as deep as possible before backtracking. It uses a stack — either explicit (iterative) or the call stack (recursive).

Graph: 0 — 1 — 3
       |
       2

DFS from 0: [0, 1, 3, 2]  (dive into 1 fully before visiting 2)

Recursive DFS

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

    def _dfs(node):
        seen.add(node)
        visited.append(node)
        for nb in graph[node]:
            if nb not in seen:
                _dfs(nb)

    _dfs(start)
    return visited

Properties

DFS vs BFS

• BFS is ideal for finding the shortest path in unweighted graphs
• DFS is ideal for cycle detection, topological sort, and SCC
• Both visit all nodes in O(V + E)

Applications

• Cycle detection
• Topological sorting
• Maze solving
• Connected components
• Finding strongly connected components

Your Task

Implement dfs(graph, start) that returns all reachable nodes in DFS order using recursion.