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

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

Сегодня мы продолжим разбирать алгоритмы на графах. Еще один очень распространенный алгоритм – поиск в глубину (DFS). Если объяснять просто, то в поиске в ширину, если помните, у нас из каждой вершины как бы выбегала толпа народа, которая потом снова делилась на большие толпы, а в поиске в глубину бегает только один неутомимый товарищ, который должен успеть оббежать все вершины в поисках нужной и очень быстро.

На первый взгляд кажется, что поиск в ширину BFS гораздо быстрее, ведь толпа может бежать сразу в нескольких направлениях, но на самом деле для большинства задач разница не очень большая, так как перед тем, как отправить толпы в нужных направлениях необходимо «остановиться и подумать» (даже в алгоритме Дейкстры найти вершину с минимальным весом), а в поиске в глубину DFS, практически не думая, сразу бежим в свободную (не посещенную ранее) вершину с минимальным номером.

При этом алгоритм поиска в глубину быстро находит путь, который не обязательно является кратчайшим. Он очень прост и хорошо подходит если надо проверить наличие пути (найти любой путь). Если же нужен кратчайший путь – применяется поиск в ширину, а лучше алгоритм Дейкстры.

На каждом шаге поиска в глубину алгоритм выбирает новую вершину, смежную с текущей и продолжает поиск уже из нее. Такое «углубление» продолжается до тех пор, пока не будет найдена вершина, смежная с конечной или алгоритм не зайдет в тупик, в этом случае он возвращается к предыдущей вершине и продолжает поиск до тех пор, пока все вершины не просмотрены.

Существуют два основных метода поиска в глубину: рекурсивный алгоритм и алгоритм с использованием стека. Чаще используется рекурсивный алгоритм.

2. Алгоритм.

Пусть надо найти путь из вершины S в вершину F.
Поиск в глубину (DFS) работает следующим образом:
Если номера вершин S и F совпали – путь найден;
Если из вершины S есть дуга вершину X и вершина X не была посещена ранее – то найти путь из X в F рекурсивно.
Второй шаг выполняется для всех вершин, в которые можно перейти из S.
Если все дуги из S обработаны и ни по одной из них не был найден путь – значит такого пути нет.

Давайте разберем пример на основе задачи про лабиринт.

Постановка задачи: Конечно, надо найти выход в лабиринте. Но работать над «сырым» лабиринтом достаточно неудобно (граф будет слишком большим и непонятным), поэтому мы разобьем его на «комнаты», соединенные между собой перегородками. Примерно так, как показано на рисунке справа.

Теперь задача приняла такой вид: есть множество комнат, между некоторыми из них можно перемещаться. Требуется найти путь из комнаты A в комнату B.

В теории графов «комнаты» называются вершинами, «переходы» между ними — ребрами. Комната А — начальная вершина, комната В — конечная.

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

Здесь овалы — это вершины (или комнаты), линии — ребра (или переходы между ними). Вершина 1 — начальная, вершина 12 — конечная.

И как же мы будем решать эту задачу?

Решение, которое сразу приходит на ум — помечать каждую вершину при входе в нее, и никогда не ходить в уже помеченные вершины — это и есть обход в глубину:

DFS (рекурсивный алгоритм).

Фрагмент кода:

internal class Program
{
    private static bool[] _uses;
    private static int[,] _graf;
    private static int _n;
    private static int _start = 0;
    private static int _end = 0;
    
    public static void Main(string[] args)
    {
        //Console.Write("Введите N=");
        //_n = Convert.ToInt32(Console.ReadLine());
        _n = 13;

        _graf = new int[_n, _n];

        //Console.Write("Введите M=");
        //int m = Convert.ToInt32(Console.ReadLine());
        int m = 11;

        /*
        for (int i = 0; i < m; i++)
        {
            Console.Write("Номер города, из которого идет дорога: ");
            _start = Convert.ToInt32(Console.ReadLine());
            Console.Write("Номер города, в который идет дорога: ");
            _end = Convert.ToInt32(Console.ReadLine());
            Console.Write("Номер города, в который идет дорога: ");
            int size = Convert.ToInt32(Console.ReadLine());
            _graf[_start, _end] = size;
            _graf[_end, _start] = size;
        }
        */

        _graf[1, 2] = 1;
        _graf[2, 1] = 1;
        _graf[2, 3] = 1;
        _graf[3, 2] = 1;
        _graf[3, 4] = 1;
        _graf[4, 3] = 1;
        _graf[4, 5] = 1;
        _graf[5, 4] = 1;
        _graf[5, 6] = 1;
        _graf[6, 5] = 1;
        _graf[6, 7] = 1;
        _graf[7, 6] = 1;
        _graf[4, 8] = 1;
        _graf[8, 4] = 1;
        _graf[8, 9] = 1;
        _graf[9, 8] = 1;
        _graf[9, 10] = 1;
        _graf[10, 9] = 1;
        _graf[10, 11] = 1;
        _graf[11, 10] = 1;
        _graf[11, 12] = 1;
        _graf[12, 11] = 1;

        //Console.Write("Введите X=");
        //_start = Convert.ToInt32(Console.ReadLine());
        _start = 1;

        //Console.Write("Введите Y=");
        //_end = Convert.ToInt32(Console.ReadLine());
        _end = 12;

        _uses = new bool[_n];

        Dfs(_start);

    }
    static void Dfs(int v)
    {
        if (_uses[v])  // Если мы здесь уже были, то тут больше делать нечего
        {
            return;
        }
        
        _uses[v] = true;   // Помечаем, что мы здесь были
        
        if (v == _end)   // Проверяем, конец ли
        {
            Console.WriteLine("Путь найден!");
            return;
        }
        
        for (int i = 0; i < _n; i++)  // Для каждого ребра
        {
            if (_graf[v, i] > 0)
            {
                 Dfs(i);  // Запускаемся из соседа
            }
        }
    }
}

Сколько ресурсов требуется алгоритму?

Алгоритм просматривает каждое ребро один раз, и выполняет для каждой вершины константное число действий. Обозначая число вершин как V, а ребер — как E, получаем, что время работы — O(V+E). Кстати, такая же сложность и у алгоритма поиска в ширину.

Глубина рекурсии, в которой мы находимся, не превышает общего числа вызовов функции DFS — числа вершин. То есть, объем памяти, необходимый для работы алгоритма, равен O(V).

Нерекурсивный DFS.

Любой рекурсивный алгоритм можно переписать в нерекурсивном виде. Вот код для DFS с использованием стека:

Фрагмент кода:

…
bool[] uses = new bool[n];

Stack<int> s = new Stack<int>();
s.Push(start);
while (s.Count > 0)
{
    int v = s.Pop();
    for (int i = 0; i < n; i++)
    {
        if (graf[v, i] > 0 && !uses[i])
        {
            s.Push(i);
            uses[i] = true;
            if (i == end)
            {
                s.Clear();
                Console.WriteLine("Путь найден!");
                break;
            }
        }
    }
}

Задание: Попробуйте самостоятельно написать алгоритм поиска в глубину с выводом в консоль номеров вершин в порядке их посещения.

Итоги занятия.