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):
    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