# 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 cycle detection.
- Connected components.
- Edge classification.

### Template

Iterative implementation using queue.

```
def dfs(root):
stack = deque([root])
while stack:
node = stack.pop()
if criterion(node): return node
for child in node.childrens:
if not constraints(child): continue
stack.append(child)
result = dfs(root)
```

Recursive implementation with a hash set memorizing visited nodes.

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

Recursive implementation builds the dfs tree on graph and topological sort order

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

Find number of components in the graph

```
def full_dfs(nodes):
for node in nodes:
if node in praent:
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