WikiZero - Пошук в глибину
- Нерекурсивні варіанти [ правити | правити код ]
- Пошук в глибину з мітками часу. Класифікація ребер [ правити | правити код ]
open wikipedia design.
Пошук в глибину ( англ. Depth-first search, DFS) - один з методів обходу графа . Стратегія пошуку в глибину, як і випливає з назви, полягає в тому, щоб йти «вглиб» графа, наскільки це можливо. Алгоритм пошуку описується рекурсивно: перебираємо всі вихідні з даної вершини ребра. Якщо ребро веде в вершину, яка не була розглянута раніше, то запускаємо алгоритм від цієї нерозглянутих вершини, а після повертаємося і продовжуємо перебирати ребра. Повернення відбувається в тому випадку, якщо в даній вершині не залишилося ребер, які ведуть в нерозглянутих вершину. Якщо після завершення алгоритму не всі вершини були розглянуті, то необхідно запустити алгоритм від однієї з нерозглянутих вершин [1] .
нехай заданий граф G = (V, E) {\ displaystyle G = (V, E)} , Де V {\ displaystyle V} - безліч вершин графа, E {\ displaystyle E} - безліч ребер графа. Припустимо, що в початковий момент часу всі вершини графа пофарбовані в білий колір. Виконаємо такі дії:
- Пройдемо по всіх вершин v ∈ V {\ displaystyle v \ in V} .
Процедура DFS (параметр - вершина u ∈ V {\ displaystyle u \ in V} )
- Перефарбовувати вершину u {\ displaystyle u} в сірий колір.
- Для будь-якої вершини w {\ displaystyle w} , суміжній з вершиною u {\ displaystyle u} і пофарбованої в білий колір, рекурсивно виконуємо процедуру DFS (w) [2] .
- Перефарбовувати вершину u {\ displaystyle u} в чорний колір.
Часто використовують двоколірні мітки - без сірого, на 1-му кроці фарбують відразу в чорний колір.
Нерекурсивні варіанти [ правити | правити код ]
На великих графах пошук в глибину серйозно навантажує стек викликів . Якщо є ризик переповнення стека , Використовують нерекурсівние варіанти пошуку.
Перший варіант: можна симулювати стек виклику програмно: для кожної з сірих вершин в стеці буде зберігатися її номер u {\ displaystyle u} і номер поточної суміжній вершини w {\ displaystyle w} .
Процедура DFS (параметр - вершина u ∈ V {\ displaystyle u \ in V} )
- Кладемо на стек пару (u, ∅) {\ displaystyle (u, \ varnothing)} . Перефарбовувати вершину u {\ displaystyle u} в сірий колір.
- Поки стік не порожній ...
- Беремо верхню пару (v, w) {\ displaystyle (v, w)} , Не витягуючи її з стека.
- Знаходимо вершину w '{\ displaystyle w'} , Суміжну з v {\ displaystyle v} і наступну за w {\ displaystyle w} .
- Якщо такої немає, витягаємо (v, w) {\ displaystyle (v, w)} з стека, перефарбовувати вершину v {\ displaystyle v} в чорний колір.
- В іншому випадку присвоюємо w: = w '{\ displaystyle w: = w'} , Прямо в стеці.
Другий варіант: можна в кожній з «сірих» вершин тримати поточний w {\ displaystyle w} і покажчик на попередню (ту, з якої прийшли).
Третій варіант працює, якщо вистачає двоколірних міток.
Процедура DFS (параметр - вершина u ∈ V {\ displaystyle u \ in V} )
- Кладемо на стек вершину u {\ displaystyle u} .
- Поки стік не порожній ...
- Беремо верхню вершину v {\ displaystyle v} .
- Якщо вона біла ...
- Перефарбовувати її в чорний колір.
- Кладемо в стек всі суміжні з v {\ displaystyle v} білі вершини.
Пошук в глибину з мітками часу. Класифікація ребер [ правити | правити код ]
Для кожної з вершин встановимо два числа - «час» входу e n t r y [u] {\ displaystyle entry [u]} і «час» виходу l e a v e [u] {\ displaystyle leave [u]} .
Модифікуємо процедуру DFS так.
- Збільшуємо «поточний час» на 1. e n t r y [u] = t {\ displaystyle entry [u] = t} .
- Перефарбовувати вершину u {\ displaystyle u} в сірий колір.
- Для будь-якої вершини v {\ displaystyle v} , суміжній з вершиною u {\ displaystyle u} і пофарбованої в білий колір, виконуємо процедуру DFS (v).
- Перефарбовувати вершину u {\ displaystyle u} в чорний колір.
- Збільшуємо «поточний час» на 1. l e a v e [u] = t {\ displaystyle leave [u] = t} .
Вважаємо, що граф орієнтований. Очевидно, для будь-якої вершини, з якої ми не вийшли в момент t, e n t r y [u] ⩽ t <l e a v e [u] {\ displaystyle entry [u] \ leqslant t <leave [u]} . Також неможливо скрёстное нерівність: e n t r y [u] <e n t r y [v] <l e a v e [u] <l e a v e [v] {\ displaystyle entry [u] <entry [v] <leave [u] <leave [v]} . Популярні на кроці 3 дуги u → v можуть бути:
Ребра неориентированного графа можуть бути ребрами дерева і зворотними, але не прямими і перехресними. [3] Щоб розрізняти ребра неорієнтованого графа, досить зазначених вище трьох-або двоколірних відміток. Ребро, що йде в білу вершину, - ребро дерева. В сіру (чорну в двокольоровому варіанті) - зворотне. В чорну - такого не буває. [4]
алгоритм Косарайю вимагає сортування вершин в зворотному порядку за часом виходу. Метка входа і типи ребер потрібні в алгоритмах пошуку точок зчленування і мостів .
Пошук в глибину обмежено застосовується як власне пошук, найчастіше на деревовидних структурах: коли відстань між точками малó, пошук в глибину може «блукати» десь далеко.
Зате пошук в глибину - хороший інструмент для дослідження топологічних властивостей графів. наприклад:
Пошук в глибину - природний вибір, коли агент (людина або робот) особисто ходить по лабіринту і бачить те, що безпосередньо поруч з ним. «Правило лівої руки» (йти, ведучи лівою рукою по стінці) буде пошуком в глибину, якщо лабіринт деревовидний (немає кружним шляхів).