Pull to refresh

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

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


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


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

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

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

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


Первое, что хочется сделать — написать перебор: в каждый момент времени находимся в какой-то вершине, и идем из нее во всех соседей:
Перебор
Предполагается, что граф хранится в массиве vector<vector<int>> edges, причем edges[v] содержит номера всех вершин, к которым есть ребро от v. Также предполагается, что в глобальной переменной finish хранится номер конечной вершины.
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,… и в какой-то момент программа просто падает из-за переполнения стека.

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


Решение, которое сразу приходит на ум — помечать каждую вершину при входе в нее, и никогда не ходить в уже помеченные вершины — это и есть обход в глубину:
DFS
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.
DFS
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);  // Запускаемся из соседа
    }
}


Тогда задача восстановления пути будет тривиальной:
get_path
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
void DFS()
{
    stack<int> s;
    s.push(start);
    while (!s.empty())
    {
        int v = s.top();
        s.pop();
        for (int i = 0; i < edges[v].size(); ++i)
        {
            if (mark[edges[v][i]] == 0)
            {
                s.push(edges[v][i]);
                mark[edges[v][i]] = 1;
            }
        }
    }
}


А что дальше?


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

Articles