Описание тега depth-first-search
Поиск в глубину (DFS) - это алгоритм обхода или поиска по дереву, древовидной структуре или графу. Каждый начинает с корня (выбирая какой-либо узел в качестве корня в случае графа) и исследует, насколько это возможно, вдоль каждой ветви перед отслеживанием с возвратом.
Поиск в глубину (DFS) - это алгоритм обхода или поиска по дереву, древовидной структуре или графу. Каждый начинает с корня (выбирая какой-либо узел в качестве корня в случае графа) и исследует, насколько это возможно, вдоль каждой ветви перед отслеживанием с возвратом.
Формально DFS - это неинформированный поиск, который прогрессирует, расширяя первый дочерний узел появляющегося дерева поиска и, таким образом, углубляясь все глубже и глубже, пока не будет найден целевой узел или пока он не достигнет узла, у которого нет дочерних узлов. Затем поиск возвращается к самому последнему узлу, который он еще не изучил. В нерекурсивной реализации все недавно развернутые узлы добавляются в стек для исследования.