DEV Community

Alex Kang
Alex Kang

Posted on

DFS Templates in Python

What is DFS?

Depth-first Search (DFS) is a tree/graph traversal algorithm that explores as far as possible in each branch.
Example of a tree
DFS traversal of the tree above would be:
[0, 1, 3, 4, 2, 5 ,6]

DFS applications

Some of the applications of DFS are:

  • traversing a explicit tree to find something
  • traversing a graph to:
    • find topological sort of graphs
    • cycle detection in graphs
    • find spanning trees
  • use backtracking to:
    • solve puzzles
    • solve combinatorial problems

Templates

We can simply traverse through the tree/graph using the following templates.

DFS on binary tree



def do_something(root):
        pass

def dfs(root):
    if not root:
        return
    do_something(root)
    dfs(root.left)
    dfs(root.right)


Enter fullscreen mode Exit fullscreen mode

DFS on N-ary tree



def do_something(root):
    pass

def get_children(root):
     pass

def dfs(root):
    if not root:
        return
    do_something(root)
    for child in get_children(root):
        dfs(child)


Enter fullscreen mode Exit fullscreen mode

DFS on graphs



visited = set()
def do_something(root):
    pass

def get_neighbors(root):
    pass

def dfs(root, visited):
    if root in visited:
        return
    do_something(root)
    visited.add(neighbor)
    for neighbor in get_neighbors(root):            
        dfs(neighbor, visited)


Enter fullscreen mode Exit fullscreen mode

In addition to simple traversals, we can also pass value up from child to parent (using return value) or pass value down from parent to child (using function parameters).

Example of passing value up (return value)

Finding max depth of N-ary tree



def get_children(root):
    pass

def max_depth(root):
    if not root:
        return 0
    depth = 0
    for child in get_children(root):
        depth = max(depth, max_depth(child))
    return depth + 1


Enter fullscreen mode Exit fullscreen mode

Example of passing value down (function parameter)

Print path on a binary tree



def dfs_path(root, res):
    if not root:
        return
    res.append(root)
    dfs_path(root.left, res)
    dfs_path(root.right, res)


Enter fullscreen mode Exit fullscreen mode

Backtracking is also a variation of DFS. Backtracking does not explore the whole tree/graph. Instead, backtracking stops exploring branches that cannot lead to a solution.

Backtracking can often be used to solve puzzles or combinatorial problems.

Backtracking template



def condition():
    pass

def do_something(root):
    pass

def get_children(root):
     pass

def backtrack(root):
    if not condition():
        return
    do_something(root)
    for child in get_children(root):
        backtrack(child)


Enter fullscreen mode Exit fullscreen mode

Top comments (0)