## 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:
1. Reachability.
2. Path finding.
3. Topological sort.
4. Directed graph cycle detection.
5. Connected components.
6. Edge classification.

### Example Code

1. 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)

1. 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):
if criterion(node): return node
for child in node.childrens:
if constraint(child): continue
if result := dfs(child): return result

result = dfs(root)

1. 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)

1. 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])

1. 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