Loading AI tools
З Вікіпедії, вільної енциклопедії
Алгори́тм по́шуку в глибину́ (англ. Depth-first search, DFS) — алгоритм для обходу дерева, структури подібної до дерева, або графу. Робота алгоритму починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину.[1]
Порядок обходу вершин. | |
Клас | Алгоритм пошуку |
---|---|
Структура даних | Граф |
Найгірша швидкодія | |
Просторова складність у найгіршому випадку |
Нехай G=(V, E) — простий зв'язний граф, усі вершини якого позначено попарно різними символами. У процесі пошуку вглиб вершинами графу G надають номери (DFS-номери) та певним способом даних для збереження множин, яку називають стеком. Зі стеку можна вилучити тільки той елемент, котрий було додано до нього останнім: стек працює за принципом «останній прийшов — перший вийшов» (LIFO). Інакше кажучи, додавання й вилучення елементів у стеку відбувається з одного кінця, який називається верхівкою стеку. DFS-номери вершини х позначають DFS(х).
Цей розділ не містить посилань на джерела. (грудень 2021) |
Наведемо кроки алгоритму
Обчислювальною складністю алгоритму (або просто складністю) назвемо кількість кроків виконуваних алгоритмом в гіршому випадку. Вона є функцією від розмірності задачі, представленої вхідними даними. Наприклад, для графу, що задається списками інцидентності, розмірність задачі представляється як пара (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 }
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.