Обход графа. Поиск в глубину. Алгоритм DFS.
Определение
Поиск в глубину - это алгоритм обхода графа, который исследует путь до тех пор, пока не достигнет самой глубокой вершины, а затем возвращается к предыдущей вершине и исследует другие пути.
Алгоритм DFS
Алгоритм DFS работает следующим образом:
- Начиная с заданной стартовой вершины, идти как можно глубже по каждому пути, пока не будет достигнута конечная вершина или пока не будут исследованы все возможные пути.
- Если вершина не была посещена ранее, она помечается как посещенная.
- Рекурсивно повторять шаги 1 и 2 для каждой посещенной соседней вершины.
Сложность алгоритма DFS также зависит от количества вершин и ребер в графе, может быть выражена как O(n+m), где n - количество вершин, а m - количество ребер.
Преимущества DFS:
- DFS может быть эффективным для поиска пути между двумя вершинами в графе.
- DFS может быть использован для топологической сортировки графа.
- DFS может быть полезен при поиске циклов в графе.
Недостатки DFS:
- DFS может зациклиться в бесконечном цикле, если граф содержит циклы.
- DFS не для нахождения кратчайшего пути между вершинами.
- DFS может потребовать больше памяти при работе с глубокими графами.
Использует стек вместо очереди, благодаря чему и получается такой принцип обхода.