### 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 cycle detection.
5. Connected components.
6. 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):
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):
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