Търсене в дълбочина (DFS)
Както вече казахме, графите моделират много проблеми от реалния живот. Затова е важно да можем да ги обхождаме (това е нещо, което различава задачите с графи в информатиката от тези в математиката). Единият от най-популярните методи е така нареченото търсене в дълбочина. Популярността му идва от простия начин на работа, а също така и лесните начини за модификация и прилагане в най-различни алгоритмични проблеми.
Идеята е следната. Започваме от произволен начален връх. След това отиваме в произволен негов съсед. От текущия връх се пробваме да обходим друг негов необходен досега съсед, в противен случай се връщаме по пътя. Тази процедура я повтаряме многократно, докато не се върнем в началния връх и всичките му съседи са вече обходени. Ще направим едно отклонение в случая на неориентирани графи. При тях е възможно да има т.нар. компоненти на свързаност.
Определение: Компоненти на свързаност на неориентиран граф наричаме максималните по включване подграфи на началния граф, така че във всеки подграф всеки два върха да са свързани. (...)
Директно от определението следва, че от произволен връх в една компонента на свързаност, можем да достигнем до всички останали върхове в компонентата, но няма как да достигнем до върхове извън компонентата на свързаност. Затова ако неориентиран граф има повече от една компоненти на свързаност, то трябва да пуснем DFS процедурата от всеки необходен връх, за да гарантираме минаването през всички компоненти. За онагледяване е показан граф с три компоненти на свързаност - една с върховете 1, 2 и 3, втора с върховете 4 и 5 и трета с върха 6. Обърнете внимание, че когато говорим за компонента на свързаност, говорим за подграф, т.е. се включват и съответните индуцирани ребра. Затова е достатъчно да асоциираме компонентата на свързаност само с върховете, които се включват, но разбираме и съответните ребра.
Следва интерактивeн пример на алгоритъма. Анимацията на DFS се пуска с бутона "Старт", като може да зададете от кой връх да започва обхождането. Преди това може да се задава ускорение от 1 до 9, както и по време на анимацията да се превърта на предишна или следваща стъпка.
Описаната идея в предната точка е рекурсивна - нека фунцията, която ще реализира идеята, наречем $dfs$. Тя ще има само един параметър - текущия връх, на който сме. Най-важният детайл е да пазим кои върхове сме обходили и затова ще имаме глобален булев масив за отбелязване $visited$. Когато отиваме в необходен съсед, отново викаме рекурсивната функция $dfs$ със следващия връх, маркираме го за обходен и продължаваме по същия начин от новия текущ връх. По този начин дори в графа да има цикли, то няма как да повтаряме върхове и алгоритъмът няма как да зацикли. Следва примерна реализация на C++:
Масивът от вектори $a$ е всъщност списъка на съседи на графа. Понеже рекурсията стъпва във всеки връх точно веднъж, то няма да имаме повече от $n$ извиквания. Това пък от своя страна означава, че сумарно работата на циклите ще е колкото броя на ребрата на графа. Така сложността на алгоритъма е $O(n+m)$.
Едно от лесните приложения, за което DFS се използва много често, е да се намери броят на свързаните компоненти на един неориентиран граф (и/или самите компоненти). Както и по-рано казахме, понякога имаме несвързани графи и за да ги обходим, трябва да пуснем DFS обхождането от всеки необходен досега връх. Но понеже имаме неориентиран граф, то като пуснем обхождането от един връх ще обходим всички върхове от компонентата, на която принадлежи върха. Съответно това означава, че с едно пускане на DFS, намираме една компонента, т.е. броя компоненти ще е равен на броя обхождания, които сме пуснали от необходени върхове. Ще покажем само броенето на компонентите с извикването на $dfs$ функцията от предната точка.
Друго приложение, което ще разгледаме, е да намерим път между два дадени върха, нека ги означим с $x$ и $y$. Ще опишем подход, който работи при произволен граф. Нека пуснем DFS обхождането от връх $x$, тогава търсим да намерим връх $y$. В момента когато стъпим на $y$, то сме намерили пътя между двата върха - достатъчно е просто да се върнем рекурсивно назад до върха, от който тръгнахме. За тази цел ще направим $dfs$ функцията да връща булев резултат дали е намерен пътя до крайния връх. Единственият останал проблем е, че ще намерим пътя в обратна посока, ако директно изведем номерата на върховете - в посока от $y$ към $x$. Затова е достатъчно в един стек $path$ да поставим върховете, когато се връщаме по пътя, и накрая да ги изведем в реда, в който са в стека. (...) Ето реализация на този алгоритъм:
Последното приложение, което ще покажем, е за откриване на това дали граф е цикличен. Нека първо разгледаме случая при неориентиран граф. По принцип главната идея е, че ако видим съсед на връх, който вече е обходен, то това ребро (...) участва в цикъл. Има само един случай, когато това може да не е вярно именно защото графът е неориентиран. Нека от връх $x$ отидем по реброто $(x,y)$ до връх $y$. Тогава в съседите на връх $y$ ще присъства и $x$, но това не оформя цикъл. Затова трябва в допълнителен параметър да пазим за всеки връх от кой сме дошли. Така в нашия случай, като сме извиквали DFS за $y$, ще сме запомнили, че сме дошли от $x$ и няма да се объркаме. Следва реализацията за неориентиран граф.
Ако търсим дали има цикъл в ориентиран граф няма как да имаме горния проблем. Дори да имаме ребра в двете посоки - $(x,y)$ и $(y,x)$, то те двете наистина образуват цикъл. Но тук има друг проблем, заради който трябва отново да променим нещо. Нека имаме следният граф.
Може да пуснете по-горе DFS върху този граф. Тогава ще се види, че за връх 2 или за връх 3 (зависи през кой минаваме първо) връх 4 ще е вече обходен, и бихме заключили, че наистина има цикъл. Ако този граф беше неориентиран, то това щеше да е вярно (защото можем да ходим и в двете посоки на ребрата). Но тук не е вярно. За да оправим алгоритъма, трябва да гледаме дали виждаме обходен връх, който е в текущия път (така е ясно, че се формира цикъл) и затова трябва да въведем вече 3 състояния на връх - 0 за необходен връх, 1 за връх в текущия път и 2 за обходен връх, който не е в текущия път. Всъщност единствено, когато напускаме връх трябва да сменяме неговото състояние на 2, другото е същото, като работата с масива $visited$. Така ще намерим цикъл само когато видим съсед, който е от текущия път, т.е. е в състояние 1. Интересното е, че другото стандартно обхождане - BFS не е удобно да се използва в случая на ориентиран граф. Затова стандартния подход за търсене на цикъл при какъвто и да е граф е да се използва DFS.
Допълнително трябва да отбележим, че трябва да пускаме горния DFS от всеки необходен връх досега. Малко е трудно с моментните знания да се даде лесна обосновка защо този алгоритъм работи коректно. Ясно е, че ако той каже, че има цикъл, това наистина е така. Обратният въпрос е по-интересен - ако каже, че няма цикъл, наистина ли е така. Това най-лесно се вижда, ако се разгледа факта, че всъщност обхождането в дълбочина строи покриващо дърво на графа и се разгледат точно кои ребра могат да затварят цикъл (те са точно тези, които се намират с тази модификация на DFS) (...).