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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене
Обхождане в дълбочина

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

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

Свойства[редактиране | edit source]

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

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

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

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

Алгоритъм[редактиране | edit source]

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

states


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

states


Пример[редактиране | edit source]

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

Graph.traversal.example.svg

Обхождането в дълбочина, започва от А при условие, че левите върхове в показаната графика се посещават преди десните, а алгоритъма запомня вече посетените възли и не преминава повторно през тях. По време на такова обхождане редът, в който ще бъдат посетени върховете е следния: A, B, D, F, E, C, G. При подобно претърсване върховете формират т.нар. дърво на Тремо, структура с широко приложение в Теорията на графите.

Извършването на същото търсене, но без запомняне на вече посетените върхове води до случай на безкраен цикъл, в който реда на посещаване е A, B, D, F, E, A, B, D, F, E и алгоритъма никога не достига до C или G. Чрез итеративно задълбочаване може да се избегне този случай и да бъдат посетени всички възли.

Псевдокод[редактиране | edit source]

В стек се задава началният връх.
Докато в стека има върхове:
       Изважда се връх от стека
       Прави се проверка в списъка с обходените и ако върхът не е обходен:
            Обхожда се и се поставя в списъка с обходените.
            Вмъкват се всички върхове, към които той има ребро в стека.

Примерна реализация на итеративна и рекурсивна версия на DFS в езика C#[редактиране | edit source]

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[редактиране | edit source]

  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);
             }
         }
     }
  }

Приложения[редактиране | edit source]

  • Намиране на свързани компоненти (Теория на графите).
  • Топологично сортиране.
  • Решения на пъзели, например намиране на един или повече изходи от лабиринт.
  • Генериране на лабиринти.
  • Намиране на мостовете в граф.
  • Откриване на двусвързаност в граф.
  • Проверка за планарност.

Източници[редактиране | edit source]

  1. http://fr.wikipedia.org/wiki/Pierre_Trémaux
  2. Наков, Преслав и др. Програмиране=++Алгоритми;. 2012. с. Глава 5.3.2. Обхождане в дълбочина.
  3. http://www.algolist.net/Algorithms/Graph/Undirected/Depth-first_search

Външни препратки[редактиране | edit source]