Претрага у дубину

Претрага у дубину (пример стабла)

Претрага у дубину (на енглеском Дептх-фирст сеарцх - ДФС) је алгоритам за претрагу структура података (стабла и графова). Почетак алгоритма је у корену стабла (код графа се неки чвор одреди за корен), а затим се претражује дуж свих грана колико год је то могуће пре повратка у корен.

Француски математичар Цхарлес Пиерре Трéмауx (19. век) је истраживао верзију овог алгоритма за проблем изласка из лавиринта.

Формална дефиниција

Обилазак започиње из произвољног задатог чвора $r$, корена претраге у дубину. Корен се означава као посећен. Затим се бира произвољни неозначени чвор $r$₁, суседан са $r$, па се из чвора $r$₁ рекурзивно стартује претрага у дубину. Из неког нивоа рекурзије излази се кад се наиђе на чвор у коме су сви суседи (ако их има) већ означени. Ако су у тренутку завршетка претраге из $r$₁, сви суседи чвора $r$ означени, онда се претрага за чвор $r$ завршава. У противном, бира се следећи произвољни неозначени сусед $r$₂ чвора $r$, извршава се претрага полазећи од $r$₂, итд.

Временска и просторна анализа

Временска и просторна анализа претраге у дубину разликује се од подручја примене самог алгоритма. У теоријском рачунарству обично се користи за проласке кроз целе графове и за то је потребно време линеарно величини графа. Код тих апликација је просторна сложеност велика јер се чувају чворови тренутне путање, као и скуп већ посећених чворова. У овом случају су временска и просторна сложеност иста као код претраге у ширину (БФС) и избор који од ова два алгоритма користити мање зависи од сложености а више од тога шта који алгоритам даје на крају.

Пример

За следећи граф:

претрага у дубину почиње од чвора А, уз претпоставку да се леве ивице бирају пре десних ивица графа и да претрага памти претходно посећене чворове па их неће понављати. Чворови ће бити посећени у следећем редоследу: А, Б, D, Ф, Е, C, Г. Гране кроз које се прошло формирају Трéмауx стабло, структуру са важним применама у теорији графова.

Исто претраживање без памћења претходно посећених чворова изгледа овако: А, Б, D, Ф, Е, А, Б, D, Ф, Е, итд. заувек, запетљано у А, Б, D, Ф, Е циклус. Оваква претрага никад неће посетити чворове C и Г.

Повратне вредности претраге у дубину

Након претраге у дубину добијамо одговарајуће разапињујуће стабло. У том стаблу постоје четири врсте грана:

1. грана стабла (повезује оца са сином)
2. повратна грана (повезује потомка са претком)
3. директна грана (повезује претка са потомком)
4. попречна грана (повезује чворове који нису сродници у стаблу)

Псеудокод алгоритма

Улаз: граф Г и његов чвор в Излаз: граф претраге у дубину 1 функција ПретрагаУДубину(Г,в):

2      označi v kao posećen
3      for sve grane e u G.obižnjeGrane(v) do
4          if grane e je neposećena then
5              w ← G.obižnjiČvor(v,e)
6              if čvor w je neposećen then
7                  označi e kao posećen
8                  rekurzivan poziv PretragaUDubinu(G,w)
9              else
10                 označi e kao zadnju granu

Не рекурзивна имплементација претраге у дубину:

1  funkcija PretragaUDubinu-iterativno(G,v):
2      označi v kao posećen
3      neka S bude stek
4      S.push(v)
5      while S nije prazan        
6            t ← S.top 
7            if t ono što tražimo:
8                return t
9            for sve grane e u G.obližnjeGrane(t) do
10               if grana e već označena 
11                   continue sa sledećom granom
12               w ← G.obližnjiČvor(t,e)
13               if čvor w nije otkriven i nije posećen
14                   označi e kao ivicu stabla
15                   označi w kao otkriven
16                   S.push(w)
17                   continue at 5
18               else if čvor w is otkriven
19                   označi e kao zadnja ivica
20               else
21                   // čvor w je posećen
22                   označi e kao napred ili kros ivica
23           označi t kao posećen
24           S.pop()

Примене

Неки алгоритми који користе претрагу у дубину као градивни елемент:

• Проналажење повезаних компоненти
• Тополошко сортирање
• Проналажење две (гране или чвора) повезане компоненте.
• Проналажење три (гране или чвора) повезане компоненте.
• Проналажење мостова графа
• Проналажење снажно-повезаних компоненти
• Решавање загонетки са само једним решењем (нпр. лавиринт)
• Генерисање лавирината

Литература

• Тхомас Х. Цормен, Цхарлес Е. Леисерсон, Роналд L. Ривест, анд Цлиффорд Стеин. Интродуцтион то Алгоритхмс, Сецонд Едитион. МИТ Пресс анд МцГраw-Хилл, 2001.
• Кнутх, Доналд Е. (1997), Тхе Арт Оф Цомпутер Программинг Вол 1. 3рд ед, Бостон: Аддисон-Wеслеy
• Гоодрицх, Мицхаел Т. (2001), Алгоритхм Десигн: Фоундатионс, Аналyсис, анд Интернет Еxамплес, Wилеy
• Живковић, Миодраг, Алгоритми, Математички Факултет у Београду