Графы для самых маленьких: DFS

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

Постановка задачи

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

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

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

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

Первое, что хочется сделать — написать перебор: в каждый момент времени находимся в какой-то вершине, и идем из нее во всех соседей:

void travel(int v)
{
    if (v == finish)   // Проверяем, конец ли
    {
        cout << "Hooray! The path was found!n";
        return;
    }
    for (int i = 0; i < (int)edges[v].size(); ++i)  // Для каждого ребра
    {
        travel(edges[v][i]);  // Запускаемся из соседа
    }
}

Увы, этот код не работает уже на графе из трех вершин, в котором ребрами соединена каждая вершина с каждой — при запуске от вершины 1 мы заходим в вершину 2, из нее — в вершину 1, из нее — опять в вершину 2,… и в какой-то момент программа просто падает из-за переполнения стека.

Что же делать?

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

void DFS(int v)
{
    if (mark[v] != 0)  // Если мы здесь уже были, то тут больше делать нечего
    {
        return;
    }
    mark[v] = 1;   // Помечаем, что мы здесь были
    if (v == finish)   // Проверяем, конец ли
    {
        cout << "Hooray! The path was found!n";
        return;
    }
    for (int i = 0; i < (int)edges[v].size(); ++i)  // Для каждого ребра
    {
        DFS(edges[v][i]);  // Запускаемся из соседа
    }
}

И что с того?

Да, программа прошла по какому-то пути, но как определить, по какому?
Будем для каждой вершины запоминать, откуда мы в нее пришли, в специальном массиве prior.

void DFS(int v, int from)
{
    if (mark[v] != 0)  // Если мы здесь уже были, то тут больше делать нечего
    {
        return;
    }
    mark[v] = 1;   // Помечаем, что мы здесь были
    prior[v] = from;  // Запоминаем, откуда пришли
    if (v == finish)   // Проверяем, конец ли
    {
        cout << "Hooray! The path was found!n";
        return;
    }
    for (int i = 0; i < (int)edges[v].size(); ++i)  // Для каждого ребра
    {
        DFS(edges[v][i], v);  // Запускаемся из соседа
    }
}

Тогда задача восстановления пути будет тривиальной:

vector<int> get_path()
{
    vector<int> ans;
    for (int v = finish; v != start; v = prior[v])  // Проходим по пути из конца в начало
    {
        ans.push_back(v);  // Запоминаем вершину
    }
    ans.push_back(start);
    reverse(ans.begin(), ans.end());  // Переворачиваем путь
    return ans;
}

А почему это работает?

Алгоритм всегда найдет путь до вершины, если он существует. Доказательство:
Для произвольного графа G:
База. Пути из не более, чем 1 вершины алгоритм находит верно (путь от начальной вершины до нее же).
Предположение: Алгоритм посещает все вершины, находящиеся на расстоянии не более, чем k — 1, от начальной.
Шаг: Рассмотрим любую вершину v, находящуюся на расстоянии k от начальной. Она, очевидно, соединена ребром с какой-то вершиной, находящейся на расстоянии k — 1 от начальной — назовем ее w. Значит, мы перейдем в вершину v при просмотре вершины w.

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

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

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

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

А что дальше?

Надеюсь, было познавательно. В следующих статьях я постараюсь рассказать побольше о том, какие задачи можно решать с помощью DFS, а также зачем нужны BFS, Dijkstra и другие алгоритмы на графах.

Автор: alexeykuzmin0

Источник