Пошук у глибину

Пошук у глибину
	Порядок обходу вершин.
Клас	Алгоритм пошуку
Структура даних	Граф
Найгірша швидкодія
Просторова складність у найгіршому випадку

Алгори́тм по́шуку в глибину́ (англ. Depth-first search, DFS) — алгоритм для обходу дерева, структури подібної до дерева, або графу. Робота алгоритму починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину.^[1]

Опис

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

Алгоритм

Наведемо кроки алгоритму

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

Псевдокод

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

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
}