Реализация топологической сортировки и поиск компонент сильной связности графа

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

Топологическая сортировка

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

Реализация топологической сортировки на c++ с использованием стека

Функция инициирования

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

vector<int> topologySortInit(graphNotWeighted &G) {
    int n = G.size();
    vector<int> resultOrder;
    vector<char> color(n, 'w');

    for (int v = 0; v < n; v++)
        if (color[v] == 'w')
            topologySortProc(G, v, color, resultOrder);

    reverse(resultOrder.begin(), resultOrder.end());

    return resultOrder;
}

Процедура топологической сортировки

void topologySortProc(graphNotWeighted &G, int start, vector<char> &color, vector<int> &order) {
    stack<pair<int, int> > S;

    S.push(make_pair(start, -1));
    color[start] = 'g';
    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 && color[G[v][i]] == 'w') {
                w = G[v][i];
                break;
            }

        if (w == -1) {
            S.pop();
            color[v] = 'b';
            order.push_back(v);
        }
        else {
            S.top().second = w;
            if (color[w] == 'w') {
                S.push(make_pair(w, -1));
                color[w] = 'g';
            }
        }
    }

    return;
}

Поиск компонент сильной связности графа

Орграф называется сильно связным, если любые две его вершины сильно связны. Две вершины s и t любого графа сильно связны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы. Вот такая математическая теория по этому поводу, тоже украдена из википедии.

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

Функция транспонирования графа на C++

Получает на вход граф и возвращает транспонированный.

graphNotWeighted transposingGraph(graphNotWeighted &G) {
    int n = G.size();
    graphNotWeighted GT(n);

    vector<int> count(n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < G[i].size(); j++)
            count[G[i][j]]++;

    for (int i = 0; i < n; i++)
        GT[i].reserve(count[i]);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < G[i].size(); j++)
            GT[G[i][j]].push_back(i);

    return GT;
}

Функция получения компоненты графа на C++

Получает на вход граф, стартовую вершину и массив цветов всех вершин графа. Находит и возвращает компоненту графа, содержащую стартовую вершину. Работает на стеке.

graphNotWeighted getComponent(graphNotWeighted &G, int start, vector<char> &color) {
    stack<pair<int, int> > S;
    graphNotWeighted component(G.size());

    bool isEmpty = false;
    for(int p = 0; p < G[start].size(); p++)
        if(color[G[start][p]] == 'w')
            isEmpty = true;

    if(isEmpty == false) {
        component[start].push_back(start);
        color[start] = 'b';
        return component;
    }

    S.push(make_pair(start, -1));
    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 && color[G[v][i]] == 'w') {
                w = G[v][i];
                break;
            }

        if (w == -1) {
            S.pop();
            color[v] = 'b';
        }
        else {
            S.top().second = w;
            if (color[w] == 'w') {
                component[w].push_back(v);
                S.push(make_pair(w, -1));
                color[w] = 'g';
            }
        }
    }

    return component;
}

Функция получения компонент сильной связности графа

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

vector<graphNotWeighted> strongConnectedComponents(graphNotWeighted &G) {
    int n = G.size();

    vector<int> order = topologySortInit(G);

    graphNotWeighted GT = transposingGraph(G);

    vector<graphNotWeighted> strongConnectedComponents;
    vector<char> color(n, 'w');
    for (int i = 0; i < n; i++)
        if (color[order[i]] == 'w')
            strongConnectedComponents.push_back(getComponent(GT, order[i], color));

    return strongConnectedComponents;
}

Заключение

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