Что такое DFS?
Поиск в глубину (DFS) — это алгоритм обхода дерева/графа, который исследует как можно дальше в каждой ветви.
Приведенное выше дерево можно обойти с помощью DFS:
Применение DFS
Некоторые из применений DFS следующие:
- обход явного дерева для поиска чего-либо
- обход графа для:
- найти топологическую сортировку графов
- обнаружение циклов в графах
- поиск прямых деревьев
- использовать обратный путь для:
- решать головоломки
- решать комбинаторные задачи
Шаблоны
Мы можем просто перемещаться по дереву/графу, используя следующие шаблоны.
DFS на двоичном дереве
def do_something(root):
pass
def dfs(root):
if not root:
return
do_something(root)
dfs(root.left)
dfs(root.right)
DFS на N-ариевом дереве
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 на графах
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)
В дополнение к простым обходам, мы также можем передавать значение вверх от дочернего элемента к родительскому (используя возвращаемое значение) или передавать значение вниз от родительского элемента к дочернему (используя параметры функции).
Пример передачи значения вверх (возвращаемое значение)
Определение максимальной глубины N-арного дерева
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
Пример передачи значения вниз (параметр функции)
Печать пути на двоичном дереве
def dfs_path(root, res):
if not root:
return
res.append(root)
dfs_path(root.left, res)
dfs_path(root.right, res)
Обратный путь также является разновидностью DFS. При бэктрекинге не исследуется все дерево/граф. Вместо этого, при бэктрекинге прекращается исследование ветвей, которые не могут привести к решению.
Бэктрекинг часто используется для решения головоломок или комбинаторных задач.
Обратный путь
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)