Обхождане в дълбочина () е алгоритъм за обхождане на структури от данни, и по-специално дърво и граф. За реализация на алгоритъма се избира даден връх (възел) от структурата, който се обозначава като корен (връх без предшественици) и обхождането стартира от него. Последователно се посещават всички следващи върхове до достигането на връх без наследници (от който не излизат ребра), след което се осъществява търсене с връщане назад () до достигане на нова крайна точка или при цялостно реализирано обхождане – към корена.
Шарл Пиер Тремо прилага версия на алгоритъма през 19 век за решаване на задачи с лабиринти.
Свойства Времевият и пространствен анализ на търсенето в дълбочина е в пряка зависимост от областта на приложение. В теоретичните компютърни науки, търсенето в дълбочина се прилага за цялостно обхождане на граф, където времето за обхождане е в линейна зависимост от броя елементи (). По отношение на пространството () в най-лошия възможен сценарий при прилагането на алгоритъма в стека се съхраняват както всички възли по текущата пътека, така и всички вече посетени такива. На стр. 276 в книгата „Програмиране = ++Алгоритми;“ от Преслав Наков и Панайот Добриков е представена таблица, която ще бъде интерпретирана за конкретния алгоритъм:
Матрица на съседство Списък на наследниците Списък на ребратаОбхождане в дълбочина
Тя онагледява сложността при обхождане на граф в зависимост от представянето. Видимо е, че в случая времевите и пространствени изисквания както за обхождането в дълбочина, така и при обхождане в ширина са идентични и избора кой алгоритъм да бъде приложен, не е пряко свързан със сложността, а с търсената подредба.
При приложението на алгоритъма за решение на задачи, свързани с търсене в области като изкуствения интелект възникват проблеми с дължината на обхожданата пътека, тъй като тя, поради своето естество е или прекалено дълга за обхождане, или в целостта си е на практика безкрайна. В такива случаи търсенето се задава до определена дълбочина, а поради ограничения в паметта не се използват структури от данни, които пазят информация за вече посетените върхове. В това си приложение обхождането в дълбочина запазва линейната си зависимост от броя на елементите (с тази особеност, че броят им не съвпада с размера на графа, тъй като някои от възлите се посещават повече от веднъж, а други нито един път). За сметка на това пространствената сложност е пропорционална на зададената дълбочина, в пъти по-малка от тази, реализирана при претърсване до идентична дълбочина чрез обхождане в ширина. Пример за удачно приложение на DFS в търсенето са евристични методи за избор на подходящо разклонение. Когато подходящата дълбочина на претърсване не е предварително известна се прилага итеративно решение на обхождане в дълбочина с поетапно увеличаване на границите. При повече от един фактор за разклонение, итеративното задълбочаване увеличава времето за изпълнение на алгоритъма с константна величина над базовия случай, а коректната стойност на дълбочинния лимит бива намирана чрез геометричното нарастване на броя върхове за всяко равнище.
Алгоритъм В DFS, всеки връх има три възможни цвята, представляващи различните му състояния:
Първоначално състоянието на всички елементи е „непосетен“ (бял). DFS започва изпълнението си от произволен връх. 1. Маркира връх u в сиво (посетен). 2. За всяко ребро (u,v), където u е бяло, DFS се изпълнява рекурсивно за u. 3. Маркира връх u в черно и връщане към горния елемент.
Пример В следния граф:
Обхождането в дълбочина, започва от А при условие, че левите върхове в показаната графика се посещават преди десните, а алгоритъма запомня вече посетените възли и не преминава повторно през тях. По време на такова обхождане редът, в който ще бъдат посетени върховете е следния: A, B, D, F, E, C, G. При подобно претърсване върховете формират т.нар. дърво на Тремо, структура с широко приложение в Теорията на графите.
Извършването на същото търсене, но без запомняне на вече посетените върхове води до случай на безкраен цикъл, в който реда на посещаване е A, B, D, F, E, A, B, D, F, E и алгоритъма никога не достига до C или G. Чрез итеративно задълбочаване може да се избегне този случай и да бъдат посетени всички възли.
Псевдокод В стек се задава началният връх.
Докато в стека има върхове: Изважда се връх от стека Прави се проверка в списъка с обходените и ако върхът не е обходен: Обхожда се и се поставя в списъка с обходените. Вмъкват се всички върхове, към които той има ребро в стека.
Примерна реализация на итеративна и рекурсивна версия на DFS в езика C# class Program { static int[][] graph = { new [] { 1, 6, 7 }, new [] { 0, 2, 5 }, new [] { 1, 3, 4 }, new [] { 2 }, new [] { 2 }, new [] { 1 }, new [] { 0 }, new [] { 0, 8, 11 }, new [] { 7, 9, 10 }, new [] { 8 }, new [] { 8 }, new [] { 7 },
static bool[] visited = new bool[graph.Length];
static void DfsRecursive(int node)
visited[node] = true;
Console.WriteLine(node);
foreach (int neighbor in graph[node])
if (visited[neighbor])
continue;
DfsRecursive(neighbor);
static void DfsIterative(int node)
var stack = new Stack<int>();
stack.Push(node);
while (stack.Count != 0)
int currentNode = stack.Pop(); visited[currentNode] = true;
Console.WriteLine(currentNode);
foreach (int neighbor in graph[currentNode].Reverse())
if (visited[neighbor])
continue;
stack.Push(neighbor);
Примерна реализация на DFS в езика Java public static void dfs(Node node, Node goal) { if (node.equals(goal)) { System.out.println(node)); } else { for (int i = 0; i < node.getNode().size(); i++) { if (stack.add(node.getNode().get(i))) { dfs(node.getNode().get(i), goal);
Приложения Намиране на свързани компоненти (Теория на графите). Топологично сортиране. Решения на пъзели, например намиране на един или повече изходи от лабиринт. Генериране на лабиринти. Намиране на мостовете в граф. Откриване на двусвързаност в граф. Проверка за планарност.
Източници
Външни препратки "Въведение в програмирането със C#" – Глава 17. Дървета и графи; Лекция: Обхождане на графи; Телерик Алго академия, февруари 2013 Algorithms and Data Structures
Категория:Алгоритми за граф Категория:Алгоритми за търсене