# Depth-First Search — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/dfs

> Follow one path as deep as possible, then backtrack — natural for recursion.

## Go deep, then back up

DFS dives down one branch until it dead-ends, then retreats to the last unexplored fork. Implemented with recursion (the call stack) or an explicit stack. `O(V + E)`.

## Recursive DFS

Mark on entry; recurse into unvisited neighbours.

```python
def dfs(g, node, seen=None):
    if seen is None: seen = set()
    seen.add(node)
    for nb in g[node]:
        if nb not in seen:
            dfs(g, nb, seen)
    return seen
```

## What DFS is good at

Detecting cycles, counting connected components, topological sort, path existence, and any exhaustive "try all combinations" search (which is backtracking).

**Quiz:** You need the shortest path in an unweighted graph. Use...

- [ ] DFS
- [x] BFS
- [ ] Either works equally

*Answer:* BFS. BFS explores in order of distance, so the first time it reaches the target is a shortest path. DFS gives no such guarantee.