Поиск в глубину ( DFS ) — это алгоритм для обхода или поиска структур данных в виде дерева или графа, который использует идею обратного отслеживания. Он исследует все узлы, продвигаясь вперед, если это возможно, или использует обратное отслеживание.
Примечание. Его можно реализовать с помощью стека .
Алгоритм
Вот шаги для алгоритма DFS :
-
Выберите узел и поместите все его соседние узлы в стек.
-
Извлеките узел из стека и вытолкните все его смежные узлов в стек.
-
Повторяйте этот процесс до тех пор, пока стек не станет пустым или пока вы не достигнете цели.
Программа может застрять в бесконечном цикле, если узел повторно посещен и ранее не был отмечен как посещенный . Следовательно, предотвратите исследование посещенных узлов, пометив их как посещенные.
Пример
У нас есть ориентированный граф из пяти узлов с G — узел для поиска. Узлы будут помечены как посещенные с помощью массива посещено , а соседние узлы будут добавлены в stack.
1 из 8
Пояснение
Начиная с исходного узла A , мы продолжаем двигаться к соседним узлам От A до B до D , где мы достигаем самого дальнего уровня. Затем мы возвращаемся к предыдущему узлу B и выбираем соседний узел. Еще раз, мы исследуем до самого дальнего уровня, где мы достигаем желаемого узла G .
Временная сложность
Временная сложность DFS при обходе всего дерева — O ( V ) O (V) O (V ) где V — количество узлов. В случае графа временная сложность составляет O ( V + E ) O (V + E ) O (V + E), где V — количество вершин, а E — количество края.
