Обхождане в дълбочина

Обхождане в дълбочина (на английски: Depth-First Search (DFS)) е алгоритъм за обхождане на структури от данни, и по-специално дърво и граф. За реализация на алгоритъма се избира даден връх (възел) от структурата, който се обозначава като корен (връх без предшественици) и обхождането стартира от него. Последователно се посещават всички следващи върхове до достигането на връх без наследници (от който не излизат ребра), след което се осъществява търсене с връщане назад (на английски: backtracking) до достигане на нова крайна точка или при цялостно реализирано обхождане – към корена.

Обхождане в дълбочина

Шарл Пиер Тремо прилага версия на алгоритъма през 19 век за решаване на задачи с лабиринти.

Свойства

Времевият и пространствен анализ на търсенето в дълбочина е в пряка зависимост от областта на приложение. В теоретичните компютърни науки, търсенето в дълбочина се прилага за цялостно обхождане на граф, където времето за обхождане е в линейна зависимост от броя елементи ($O(|E|)$). По отношение на пространството ($O(|V|)$) в най-лошия възможен сценарий при прилагането на алгоритъма в стека се съхраняват както всички възли по текущата пътека, така и всички вече посетени такива. На стр. 276 в книгата „Програмиране = ++Алгоритми;“ от Преслав Наков и Панайот Добриков е представена таблица, която ще бъде интерпретирана за конкретния алгоритъм:

	Матрица на съседство	Списък на наследниците	Списък на ребрата
Обхождане в дълбочина	$\Theta (n^{2})$	$\Theta (n+m)$	$\Theta (n*m)$

Тя онагледява сложността при обхождане на граф в зависимост от представянето. Видимо е, че в случая времевите и пространствени изисквания както за обхождането в дълбочина, така и при обхождане в ширина са идентични и избора кой алгоритъм да бъде приложен, не е пряко свързан със сложността, а с търсената подредба.

При приложението на алгоритъма за решение на задачи, свързани с търсене в области като изкуствения интелект възникват проблеми с дължината на обхожданата пътека, тъй като тя, поради своето естество е или прекалено дълга за обхождане, или в целостта си е на практика безкрайна. В такива случаи търсенето се задава до определена дълбочина, а поради ограничения в паметта не се използват структури от данни, които пазят информация за вече посетените върхове. В това си приложение обхождането в дълбочина запазва линейната си зависимост от броя на елементите (с тази особеност, че броят им не съвпада с размера на графа, тъй като някои от възлите се посещават повече от веднъж, а други нито един път). За сметка на това пространствената сложност е пропорционална на зададената дълбочина, в пъти по-малка от тази, реализирана при претърсване до идентична дълбочина чрез обхождане в ширина. Пример за удачно приложение на DFS в търсенето са евристични методи за избор на подходящо разклонение. Когато подходящата дълбочина на претърсване не е предварително известна се прилага итеративно решение на обхождане в дълбочина с поетапно увеличаване на границите. При повече от един фактор за разклонение, итеративното задълбочаване увеличава времето за изпълнение на алгоритъма с константна величина над базовия случай, а коректната стойност на дълбочинния лимит бива намирана чрез геометричното нарастване на броя върхове за всяко равнище.

Алгоритъм

В DFS, всеки връх има три възможни цвята, представляващи различните му състояния:

states

Първоначално състоянието на всички елементи е „непосетен“ (бял). DFS започва изпълнението си от произволен връх.
1. Маркира връх u в сиво (посетен).
2. За всяко ребро (u,v), където u е бяло, DFS се изпълнява рекурсивно за u.
3. Маркира връх u в черно и връщане към горния елемент.

states

Пример

В следния граф:

Обхождането в дълбочина, започва от А при условие, че левите върхове в показаната графика се посещават преди десните, а алгоритъма запомня вече посетените възли и не преминава повторно през тях. По време на такова обхождане редът, в който ще бъдат посетени върховете е следния: 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