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

Претрага у дубину (на енглеском Дептх-фирст сеарцх - ДФС) је алгоритам за претрагу структура података (стабла и графова). Почетак алгоритма је у корену стабла (код графа се неки чвор одреди за корен), а затим се претражује дуж свих грана колико год је то могуће пре повратка у корен.
Француски математичар Цхарлес Пиерре Трéмауx (19. век) је истраживао верзију овог алгоритма за проблем изласка из лавиринта.
Формална дефиниција
[уреди | уреди извор]Обилазак започиње из произвољног задатог чвора , корена претраге у дубину. Корен се означава као посећен. Затим се бира произвољни неозначени чвор 1, суседан са , па се из чвора 1 рекурзивно стартује претрага у дубину. Из неког нивоа рекурзије излази се кад се наиђе на чвор у коме су сви суседи (ако их има) већ означени. Ако су у тренутку завршетка претраге из 1, сви суседи чвора означени, онда се претрага за чвор завршава. У противном, бира се следећи произвољни неозначени сусед 2 чвора , извршава се претрага полазећи од 2, итд.
Временска и просторна анализа
[уреди | уреди извор]Временска и просторна анализа претраге у дубину разликује се од подручја примене самог алгоритма. У теоријском рачунарству обично се користи за проласке кроз целе графове и за то је потребно време линеарно величини графа. Код тих апликација је просторна сложеност велика јер се чувају чворови тренутне путање, као и скуп већ посећених чворова. У овом случају су временска и просторна сложеност иста као код претраге у ширину (БФС) и избор који од ова два алгоритма користити мање зависи од сложености а више од тога шта који алгоритам даје на крају.
Пример
[уреди | уреди извор]За следећи граф:
претрага у дубину почиње од чвора А, уз претпоставку да се леве ивице бирају пре десних ивица графа и да претрага памти претходно посећене чворове па их неће понављати. Чворови ће бити посећени у следећем редоследу: А, Б, D, Ф, Е, C, Г. Гране кроз које се прошло формирају Трéмауx стабло, структуру са важним применама у теорији графова.
Исто претраживање без памћења претходно посећених чворова изгледа овако: А, Б, D, Ф, Е, А, Б, D, Ф, Е, итд. заувек, запетљано у А, Б, D, Ф, Е циклус. Оваква претрага никад неће посетити чворове C и Г.
Повратне вредности претраге у дубину
[уреди | уреди извор]Након претраге у дубину добијамо одговарајуће разапињујуће стабло. У том стаблу постоје четири врсте грана:
- грана стабла (повезује оца са сином)
- повратна грана (повезује потомка са претком)
- директна грана (повезује претка са потомком)
- попречна грана (повезује чворове који нису сродници у стаблу)
Псеудокод алгоритма
[уреди | уреди извор]Улаз: граф Г и његов чвор в Излаз: граф претраге у дубину 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
- Живковић, Миодраг, Алгоритми, Математички Факултет у Београду