Редагування Пошук у глибину

[[Файл:Depth-first-tree.svg|thumb|right|300px|Порядок обходу вершин.]]
{{Алгоритми пошуку графами}}

'''Алгори́тм пошуку́ в глибину́''' ({{lang-en|Depth-first search, DFS}}) — [[алгоритм]] для обходу [[Дерево (структура даних)|дерева]], структури подібної до дерева, або [[Граф (математика)|графа]]. Робота алгоритму починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину.<ref name="mit">{{cite book
|автор=''Thomas H. Cormen'', ''Charles E. Leiserson'', ''Ronald L. Rives''t, ''Clifford Stein''
|рік=2001
|назва=Introduction to Algorithms
| розділ=22.3
|видання=2-ге
|мова={{lang-en|}}
|сторінки=540-549
|видавництво=MIT Press
|isbn=0-262-03293-7}} </ref>

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

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

== Обчислювальна складність алгоритму ==
Обчислювальною складністю алгоритму (або просто складністю) назвемо кількість кроків виконуваних алгоритмом в гіршому випадку. Вона є функцією від розмірності задачі, представленої вхідними даними. Наприклад, для графа, що задається списками інцидентності, розмірність задачі представляється як пара (n, m). Складність алгоритму визначається, як функція f, така, що f (n, m) дорівнює числу кроків алгоритму для довільного графа з n вершинами і m ребрами. Під кроком алгоритму розуміється машинна команда, і при такому визначенні кроку обчислювальна складність залежить від конкретної системи команд і способу трансляції. Нас же буде надалі цікавити не точна складність алгоритму, обчислення якої практично неможливо, а асимптотична складність, яка визначається швидкістю росту числа кроків алгоритму при необмеженому збільшенні розмірності задачі. Крім того, обчислювальна складність алгоритму, обчислена при різних системах команд або способах трансляції, відрізняються один від одного в p разів, де p - речова константа, а їх швидкість росту однакова.
Для порівняння швидкості росту двох функцій 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)

== Псевдокод ==
Рекурсивна версія алгоритму:<ref>див. алгоритм наведений на англ. вікі.</ref>

 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}}

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