Реализация алгоритма поиска в глубину на графе

Краткое описание алгоритма поиска в глубину

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

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

Моя реализация поиска в глубину на c++

Представление графа аналогично представлению в поиске в ширину. В виде списка смежности.

typedef vector<vector<int> > graphNotWeighted;

Далее буду представлены две реализации: с рекурсивным обходом и с линейным.

Исходный код алгоритма на c++

Функция инициирования обхода в глубину

Функция принимает граф и флаг, который указывает на рекурсивность обхода. Инициализирует все вспомогательные массивы и запускает процедуру обхода. Алгоритм работает через покраску вершин, подробно его описывать не буду, на википедии есть славная статья.

//Отметка времени
int currentTime = 0;

void DFSInit(graphNotWeighted &G, bool recursive) {
    int n = G.size();
    //Расстояние от i-ой вершины до стартовой
    vector<int> distance(n, -1);
    //Предок i-ой вершины на пути к стартовой
    vector<int> prevTop(n, -1);
    vector<int> time(n, -1);
    //Цвет i-ой вершины
    vector<char> topColor(n, 'w');

    currentTime = 0;

    for(int v = 0; v < n; v++) {
        if(topColor[v] == 'w') {
            if(recursive == true) {
                DFSRecursive(G, v, distance, prevTop, time, topColor);
            }
            else {
                DFSInStack(G, v, distance, prevTop, time, topColor);
            }
        }
    }

    //Print results
    for (int i = 0; i < prevTop.size(); i++) {
        cout << i << '(' << distance[i] << ',' << time[i] << ")  :";
        int x = prevTop[i];
        while (x != -1) {
            cout << x << ' ';
            x = prevTop[x];
        }
        cout << endl;
    }
    cout << endl;

    return;
}

Рекурсивный вариант обхода в глубину

void DFSRecursive(
        graphNotWeighted &G,
        int start,
        vector<int> &distance,
        vector<int> &prevTop,
        vector<int> &time,
        vector<char> &topColor) {

    currentTime++;
    distance[start] = currentTime;
    topColor[start] = 'g';
    for (int i = 0; i < G[start].size(); i++) {
        int u = G[start][i];

        if (topColor[u] == 'w') {
            prevTop[u] = start;
            DFSRecursive(G, u, distance, prevTop, time, topColor);
        }
    }

    topColor[start] = 'b';
    currentTime++;
    time[start] = currentTime;

    return;
}

Нерекурсивный вариант обхода в глубину с использованием стека

 
void DFSInStack(
        graphNotWeighted &G,
        int start,
        vector<int> &distance,
        vector<int> &prevTop,
        vector<int> &time,
        vector<char> &topColor) {

    stack<pair<int, int> > S;

    S.push(make_pair(start, -1));
    topColor[start] = 'g';
    currentTime++;
    distance[start] = currentTime;
    while (S.size()) {
        int v = S.top().first;
        int u = S.top().second;

        int w = -1;
        for (int i = 0; i < G[v].size(); i++)
            if (G[v][i] != u && topColor[G[v][i]] == 'w') {
                w = G[v][i];
                break;
            }

        if (w == -1) {
            S.pop();
            topColor[v] = 'b';
            currentTime++;
            time[v] = currentTime;
        }
        else {
            S.top().second = w;
            if (topColor[w] == 'w') {
                prevTop[w] = v;
                S.push(make_pair(w, -1));
                currentTime++;
                distance[w] = currentTime;
                topColor[w] = 'g';
            }
        }
    }

    return;
}

Заключение

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