Перегляд вихідного коду сторінки Пошук у глибину

{{Infobox algorithm
|class=[[Алгоритм пошуку]]
|image=[[File:Depth-first-tree.svg|none|300px]]<small>Порядок обходу вершин.</small>
|data=[[Граф (математика)|Граф]]
|time=<math>O(|V| + |E|)</math>
|space=<math>O(|V|)</math>
}}
{{Алгоритми пошуку графами}}

'''Алгори́тм по́шуку в глибину́''' ({{lang-en|Depth-first search, DFS}})&nbsp;— [[алгоритм]] для обходу [[Дерево (структура даних)|дерева]], структури подібної до дерева, або [[Граф (математика)|графу]]. Робота алгоритму починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину.<ref name="mit">{{CLRS|chapter=22.3 Пошук вглиб}}</ref>

== Опис ==
Нехай G=(V, E)&nbsp;— простий [[зв'язний граф]], усі вершини якого позначено попарно різними символами. У процесі пошуку вглиб вершинам графа G надають номери (DFS-номери), які для вершини x позначають DFS(x), та певним чином позначають ребра. У процесі роботи алгоритму використовують структуру даних для збереження множин, яку називають [[стек]]ом. Зі стеку можна вилучити тільки той елемент, котрий було додано до нього останнім: стек працює за принципом «останній прийшов&nbsp;— перший вийшов» ([[Стек|LIFO]]). Інакше кажучи, додавання й вилучення елементів у стеку відбувається з одного кінця, який називається верхівкою стеку. DFS-номери вершини х позначають DFS(х).

== Алгоритм ==
{{Розділ без джерел|дата=грудень 2021}}

Наведемо кроки алгоритму
# Почати з довільної вершини v. Виконати DFS(v):=1. Включити цю вершину в стек.
# Розглянути вершину у верхівці стеку: нехай це вершина х. Якщо всі ребра, інцидентні вершині х, позначено, то перейти до кроку 4, інакше&nbsp;— до кроку 3.
# Нехай {''x'', ''y''}&nbsp;— непозначене ребро. Якщо DFS(''у'') уже визначено, то позначити ребро {''x'', ''y''} штриховою лінією та перейти до кроку 2. &nbsp;Якщо DFS(''у'') не визначено, то позначити ребро {''x'', ''y''} потовщеною суцільною лінією, визначити DFS(''у'') як черговий DFS-номер, включити цю вершину в стек і перейти до кроку 2.
# Виключити вершину х зі стеку. Якщо стек порожній, то зупинитись, інакше&nbsp;— перейти до кроку 2.

== Обчислювальна складність алгоритму ==
Обчислювальною складністю алгоритму (або просто складністю) назвемо кількість кроків виконуваних алгоритмом в гіршому випадку. Вона є функцією від розмірності задачі, представленої вхідними даними. Наприклад, для графу, що задається списками інцидентності, розмірність задачі представляється як пара (n, m). Складність алгоритму визначається, як функція f, така, що f (n, m) дорівнює числу кроків алгоритму для довільного графу з n вершинами і m ребрами. Під кроком алгоритму розуміється машинна команда, і при такому визначенні кроку обчислювальна складність залежить від конкретної системи команд і способу трансляції. Нас же буде надалі цікавити не точна складність алгоритму, обчислення якої практично неможливо, а асимптотична складність, яка визначається швидкістю росту числа кроків алгоритму при необмеженому збільшенні розмірності задачі. Крім того, обчислювальна складність алгоритму, обчислена при різних системах команд або способах трансляції, відрізняються один від одного в p разів, де p&nbsp;— речова константа, а їх швидкість росту однакова.
Для порівняння швидкості росту двох функцій f(n) i g(n) будемо використовувати позначення f(n) = O[g(n)] або f(n) = Ω[g(n)].
Будемо говорити, що функція f(n) має порядок зростання не більше, ніж функція g(n), що позначається f(n) = O[g(n)], [[Тоді й лише тоді|тоді і тільки тоді]], коли існують C = const і N > 0, такі, що |f(n)| <= C|g(n)| n>= N
Будемо говорити, що функція f(n) має порядок зростання не менше, ніж функція g(n), що позначається f(n) = Ω[g(n)], тоді і тільки тоді, коли існують C = const і N > 0, такі, що |f(n)| >= C|g(n)| n>= N
Оцінимо обчислювальну складність рекурсивного варіанту алгоритму пошуку у глибину.
O(n) + O(2m) = O(n) + O(m) = O(n+m)

== Псевдокод ==
Рекурсивна версія алгоритму:

 def dfs('''v'''):
     помітити '''v''' як відвідану
     обійти-в-прямому-порядку('''v''')
     для всіх ребер '''i''' інцидентних до '''v''' таких що '''i''' не відвідано
         dfs('''i''')
     обійти-в-зворотному-порядку('''v''')

Версія без рекурсії:

 dfs('''граф''' G)
 {
   '''список''' L = '''порожній'''
   '''дерево''' T = '''порожнє'''
   ''обрати початкове ребро x''
   пошук(x)
   '''поки'''(L '''не порожній''')
   {
     ''видалити ребро (v, w) з голови L''
     '''якщо''' ''w не відвідано''
     {
       ''додати (v, w) до T''
       пошук(w)
     }
   }
 }
    
 пошук('''вершина''' v)
 {
   ''відвідати v''
   ''для кожного ребра (v, w)''
     ''додати ребро (v, w) на початок L''
 }

== Див. також ==
* [[Список алгоритмів]]
* [[Пошук в глибину з ітеративним заглибленням]]
* [[Пошук у ширину]]
* [[Двонаправлений пошук]]
* [[Обхід дерева]]

== Примітки ==
{{reflist}}

{{Algorithms-stub}}

[[Категорія:Алгоритми пошуку]]
[[Категорія:Алгоритми на графах]]