What is DFS?
Depth-first Search (DFS) is a tree/graph traversal algorithm that explores as far as possible in each branch.
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)
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)
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)
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
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)
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)
Top comments (0)