What is depth-first search (DFS)?

Question

Accepted Answer

**DFS** explores a graph by going as deep as possible along each branch before backtracking. It uses a **stack** (often the call stack via recursion) and visits a full path before exploring alternatives.

## The idea

From a node, recurse into an unvisited neighbor, and keep going deep; when stuck, back up and try another branch.

## Example

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS vs DFS

| | BFS | DFS |
|---|-----|-----|
| Structure | queue | stack / recursion |
| Finds | shortest (unweighted) | any path |
| Memory | O(V) frontier | O(depth) |
| Good for | shortest paths, levels | cycles, topo sort, components |

## Complexity

- **Time:** O(V + E). **Space:** O(V) (recursion depth + visited).

## Pitfalls

Deep graphs can overflow the recursion stack — use an explicit stack. Track `visited` to handle cycles.

## Why it matters

DFS underpins cycle detection, topological sort, connected components, and maze/path generation.

Its recursive elegance makes tree and graph code concise.

Knowing when depth-first beats breadth-first is core graph-algorithm fluency.

	BFS	DFS
Structure	queue	stack / recursion
Finds	shortest (unweighted)	any path
Memory	O(V) frontier	O(depth)
Good for	shortest paths, levels	cycles, topo sort, components