Алгоритмы на графах: Поиск в глубину (DFS, DLS, IDDFS)

Теория графов - довольно обширная и интересная тема. Существует множество алгоритмов, используемых при работе с графами. Одни довольно простые, другие посложней. В этом цикле статей я планирую разобрать наиболее известные и широко используемые из них. Примеры программного кода будут приводиться на C#.

Здесь я писал о наиболее часто используемых способах представления графов в программах. Но в наших статьях мы будем использовать упрощенный подход, когда каждая вершина просто хранит в себе список соседних вершин. Вот его реализация:

using System;
using System.Collections.Generic;
// ...
class Node
{
    /// Имя вершины.
    public string Name { get; }
    /// Список соседних вершин.
    public List<Node> Children { get; }

    public Node(string name)
    {
        Name = name;
        Children = new List<Node>();
    }

    /// Добавляет новую соседнюю вершину.
    public Node AddChildren(Node node, bool bidirect = true)
    {
        Children.Add(node);
        if (bidirect)
        {
            node.Children.Add(this);
        }
        return this;
    }
}

Исходный код для этой статьи лежит здесь.

Введение

В этой статье мы будем использовать ориентированный не взвешенный граф, который можно увидеть ниже. Цифры - это просто номера вершин.

Опишем этот граф в программе:

static void Main(string[] args)
{
    var n01 = new Node("01");
    var n02 = new Node("02");
    var n03 = new Node("03");
    var n04 = new Node("04");
    var n05 = new Node("05");
    var n06 = new Node("06");
    var n07 = new Node("07");
    var n08 = new Node("08");
    var n09 = new Node("09");
    var n10 = new Node("10");
    var n11 = new Node("11");
    var n12 = new Node("12");
    var n13 = new Node("13");
    var n14 = new Node("14");
    var n15 = new Node("15");
    n01.AddChildren(n02).AddChildren(n03);
    n02.AddChildren(n05);
    n03.AddChildren(n04);
    n04.AddChildren(n05, false).AddChildren(n10, false).AddChildren(n11, false);
    n06.AddChildren(n01, false);
    n07.AddChildren(n03, false).AddChildren(n08);
    n09.AddChildren(n08).AddChildren(n10);
    n11.AddChildren(n12).AddChildren(n13);
    n12.AddChildren(n13);
    n14.AddChildren(n15);
}

Поиск в глубину (DFS)

Логика поиска в глубину состоит в том, чтобы найти как можно более длинную последовательность вершин. Этот алгоритм является рекурсивным.

Применение алгоритма

Непосредственно как поиск, алгоритм применяется не так часто (чаще всего для поиска в деревьях). Но поиск в глубину является основой для более сложных алгоритмов, которые мы будем рассматривать в следующих статьях.

Реализация

Вот так поиск в глубину можно представить в виде псевдокода:

  1. Берем исходную вершину и помечаем ее как посещенную.
  2. Обрабатываем вершину.
  3. Повторяем эти пункты для каждой не посещенной соседней вершины.

На следующем изображении можно увидеть очередность обхода узлов начиная из первого. Здесь цифры - это шаг, на котором посещается вершина.

В этой статье мы будем использовать поиск в глубину для поиска пути (не оптимального) между вершинами. Вот реализация этого алгоритма. Вместо составления пути можно производить любое действие с вершинами. Так же не обязательно прерывать обход - он завершиться самостоятельно, обойдя все доступные вершины.

using System;
using System.Collections.Generic;
using System.Linq;
// ...
class DepthFirstSearch
{
    // Список посещенных вершин
    private HashSet<Node> visited;
    // Путь из начальной вершины в целевую.
    private LinkedList<Node> path;
    private Node goal;

    public LinkedList<Node> DFS(Node start, Node goal)
    {
        visited = new HashSet<Node>();
        path = new LinkedList<Node>();
        this.goal = goal;
        DFS(start);
        if (path.Count > 0)
        {
            path.AddFirst(start);
        }
        return path;
    }

    private bool DFS(Node node)
    {
        if (node == goal)
        {
            return true;
        }
        visited.Add(node);
        foreach (var child in node.Children.Where(x => !visited.Contains(x)))
        {
            if (DFS(child))
            {
                path.AddFirst(child);
                return true;
            }
        }
        return false;
    }
}

Запускаем поиск:

static void Main(string[] args)
{
    // ...
    var search = new DepthFirstSearch();
    var path = search.DFS(n06, n10);
    PrintPath(path); // 06 -> 01 -> 03 -> 04 -> 10
    var path = search.DFS(n06, n14);
    PrintPath(path); // You shall not pass!
}

private static void PrintPath(LinkedList<Node> path)
{
    Console.WriteLine();
    if (path.Count == 0)
    {
        Console.WriteLine("You shall not pass!");
    }
    else
    {
        Console.WriteLine(string.Join(" -> ", path.Select(x => x.Name)));
    }
    Console.Read();
}

У поиска в глубину есть несколько модификаций.

Поиск с ограничением глубины (DLS)

Если запустить поиск в глубину на бесконечном графе, то поиск никогда не завершиться. Для избежания этой ситуации можно добавить в стандартный DFS ограничение глубины - максимальную глубину на которую он может спускаться. Плюсом этого решения является то, что мы избежим бесконечной работы. Минус заключается в том, что мы можем не найти существующий путь из-за того, что он может быть длиннее максимально допустимой глубины.

Псевдокод этого алгоритма выглядит так:

  1. Берем исходную вершину и помечаем ее как посещенную.
  2. Проверяем, что предел глубины не достигнут.
  3. Обрабатываем вершину.
  4. Повторяем эти пункты для каждой не посещенной соседней вершины.

Код выглядит так:

class DepthFirstSearch
{
    // ...
    // Был ли поиск завершен из-за того, что достиг предела глубины.
    private bool limitWasReached;

    public LinkedList<Node> DLS(Node start, Node goal, int limit)
    {
        visited = new HashSet<Node>();
        path = new LinkedList<Node>();
        limitWasReached = true;
        this.goal = goal;
        DLS(start, limit);
        if (path.Count > 0)
        {
            path.AddFirst(start);
        }
        return path;
    }

    private bool DLS(Node node, int limit)
    {
        node.Handler();
        if (node == goal)
        {
            return true;
        }
        if (limit == 0)
        {
            limitWasReached = false;
            return false;
        }
        visited.Add(node);
        foreach (var child in node.Children.Where(x => !visited.Contains(x)))
        {
            if (DLS(child, limit - 1))
            {
                path.AddFirst(child);
                return true;
            }
        }
        return false;
    }
}

Запускаем:

static void Main(string[] args)
{
    // ...
    var search = new DepthFirstSearch();
    var path = search.DFS(n06, n10, 4);
    PrintPath(path); // 06 -> 01 -> 03 -> 04 -> 10
    var path = search.DFS(n06, n10, 3);
    PrintPath(path); // You shall not pass! - Не хватает лимита глубины.
}

Поиск в глубину с итеративным углублением (IDDFS)

Поиск в глубину редко применяется для поиска пути т.к. найденный путь не обязательно будет оптимальным. Для поиска оптимального пути обычно используют другие алгоритмы. Но можно модифицировать поиск в глубину так, чтобы он искал оптимальный путь. Для этого циклично используется DLS, увеличивая ограничение глубины с каждой итерацией. В таком случае мы получим минимально необходимую глубину для нахождения пути.

Псевдокод этого алгоритма выглядит так:

  1. Устанавливаем ограничение глубины равное 1.
  2. Запускаем DLS с этим ограничением.
  3. Если путь не найден, то увеличиваем ограничение глубины на 1 и переходим к пункту 2.

Для того, чтобы определить, почему DLS не нашел пути (достиг лимита или обошел весь граф), мы добавили переменную limitWasReached. Выход из цикла происходит если был найден путь или если весь граф был обойден.

Опишем этот алгоритм:

class DepthFirstSearch
{
    // ...
     public LinkedList<Node> IDDFS(Node start, Node goal)
    {
        for (int limit = 1; ; limit++)
        {
            var result = DLS(start, goal, limit);
            if (result.Count > 0 || limitWasReached)
            {
                return result;
            }
        }
    }
}

Запускаем поиск. Обратите внимание, что в первом случае используется обычный DFS. И найденный им путь не оптимален. А IDDFS нашел оптимальный путь.

static void Main(string[] args)
{
    // ...
    var search = new DepthFirstSearch();
    var path = search.DFS(n09, n10);
    PrintPath(path); // 09 -> 08 -> 07 -> 03 -> 04 -> 10
    var path = search.IDDFS(n09, n10);
    PrintPath(path); // 09 -> 10
}

Заключение

В этой статье мы рассмотрели поиск в глубину (DFS) и его основные модификации: DFS и IDDFS. Многим эта статья может показаться наивной (все и так это знают). Но она необходима для того, чтобы заложить основу для дальнейших обсуждений. В следующей статье мы рассмотрим еще один базовый алгоритм для работы с графами - поиск в ширину.

Комментарии

Используйте Markdown
Спасибо за коментарий!
Ваше сообщение будет доступно после проверки.