# Depth First Search

## Remarks

- The depth first search algorithm traversals tree / graph by exploring the node branch / edges as far as possible before backtrack and explore other alternatives.
- DFS can be used to solve problems like:
- Reachability.
- Path finding.
- Topological sort.
- Directed graph cycle detection.
- Connected components.
- Edge classification.

### Example Code

- Iterative implementation using stack to find a node in the connected components of the starting node.

```
def criterion(node): return node.val == 123
def constraint(node): return node is not None
def dfs(root):
stack = [root]
while stack:
node = stack.pop()
if criterion(node): return node
stack.extend(filter(lambda child: not constraint(child), node.childrens))
result = dfs(root)
```

- Recursive implementation with a hash set memorizing visited nodes.

```
def constraint(node): return node is not None and node not in visited
visited = set()
def dfs(node):
visited.add(node)
if criterion(node): return node
for child in node.childrens:
if constraint(child): continue
if result := dfs(child): return result
result = dfs(root)
```

- Recursive implementation which builds the single source dfs tree on graph and gather the topological sort order.

```
parent = dict()
parent[source] = source
order = []
def dfs(node):
for nei in adj[node]:
if nei in parent: continue
parent[nei] = node
dfs(nei)
order.append(node)
dfs(source)
```

- Find number of components in the graph, uses the routine in 3.

```
def full_dfs(nodes):
for node in nodes:
if node in parent: continue
parent[node] = node
dfs(node)
num_components = len([node for node in parent if praent[node] == node])
```

- Edge Classification

- Consider a graph edge from vertex $u$ to $v$, we call the edge a
**tree edge**if the edge is part of the DFS tree (i.e. $parent[v] = u$) - Otherwise, the edge from $u$ to $v$ is not a tree edge, and is either:
- a back edge - $u$ is a descendant of $v$
- a forward edge - $v$ is a descendant of $u$
- a cross edge - neither are descendants of each other