Поиск в глубину — это алгоритм графа, используемый в топологической сортировке, задачах планирования, обнаружении циклов в графах и решении головоломок только с одним решением, таких как лабиринт или головоломка судоку.
Временная сложность
Временная сложность поиска в глубину составляет O(V+E). Где v — количество вершин, а e — количество ребер.
Объяснение
Поиск в глубину — это почти тот же алгоритм, что и поиск в ширину, и даже оба алгоритма имеют одинаковую временную сложность, единственная разница между ними состоит в том, что алгоритмы поиска в ширину проверяют узлы/вершины по уровням и поиск в глубину идет непосредственно вглубь графа.
При поиске в глубину также выполняются две основные операции
- проверка всех вершин/узлов в графе
- проверка всех ребер этого узла
- таким образом, O (V + E) - это временная сложность этого графа.
Ps: в поиске в ширину я уже написал огромное объяснение временной сложности этого графа, и то же самое можно применить и здесь.
В приведенном ниже примере кодирования я использовал неориентированный граф, тогда как в алгоритме поиска в ширину я использовал в качестве примера ориентированный граф. Но координаты графика одинаковы в обоих примерах.
