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