E028. Поиск компонент сильной связности, построение конденсации graphа

Источник: e-maxx.ru/algo, страница PDF 89.

Определения, постановка задачи

Дан ориентированный graph

, множество вершин которого

и множество рёбер —

. Петли и кратные

рёбра допускаются. Обозначим через

количество вершин graphа, через

— количество рёбер. Компонентой сильной связности (strongly connected component) называется такое (максимальное

по включению) подмножество вершин

, что любые две вершины этого подмножества достижимы друг из друга, т.е.

для

:

где символом

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

всех вершин graphа. Отсюда логично Definition конденсации

как graphа, получаемого из данного

graphа сжатием каждой компоненты сильной связности в одну вершину. Каждой вершине graphа конденсации

соответствует компонента сильной связности graphа

, а ориентированное edge между двумя vertexми

и

graphа конденсации проводится, если найдётся пара вершин

, между которыми существовало edge

в исходном graphе, т.е. . Важнейшим свойством graphа конденсации является то, что он ацикличен. Действительно, предположим,

что

, докажем, что

. Из определения конденсации получаем, что найдутся две вершины

и

, что

. Доказывать будем от противного, т.е. предположим, что

, тогда найдутся две

вершины

и

, что

. Но т.к.

и

находятся в одной компоненте сильной связности, то

между ними есть путь; аналогично для

и

. В итоге, объединяя пути, получаем, что

, и одновременно

. Следовательно,

и

должны принадлежать одной компоненте сильной связности, т.е. получили противоречие, что и требовалось доказать. Описываемый ниже Algorithm выделяет в данном graphе все компоненты сильной связности. Построить по ним graph конденсации не составит труда.

Algorithm

Описываемый здесь Algorithm был предложен независимо Косараю (Kosaraju) и Шариром (Sharir) в 1979 г. Это очень простой в реализации Algorithm, основанный на двух сериях поисков в глубину, и потому работающий за

время

. На первом шаге Algorithmа выполняется серия обходов в глубину, посещающая весь graph. Для этого мы проходимся по всем vertexм graphа и из каждой ещё не посещённой вершины вызываем обход в глубину. При

этом для каждой вершины

запомним время Outputа

. Эти времена Outputа играют ключевую роль

в Algorithmе, и эта роль выражена в приведённой ниже теореме.

Сначала введём обозначение: время Outputа

из компоненты

сильной связности определим как максимум

из значений

для всех

. Кроме того, в доказательстве теоремы будут упоминаться и времена Inputа

в каждую вершину

, и аналогично определим времена Inputа

для каждой компоненты сильной

связности как минимум из величин

для всех

.

Теорема. Пусть

и

— две различные компоненты сильной связности, и пусть в graphе конденсации между

ними есть edge

. Тогда

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

и

:

● Первой была достигнута компонента

. Это означает, что в какой-то момент времени обход в глубину заходит

в некоторую вершину

компоненты

, при этом все остальные вершины компонент

и

ещё не посещены. Но, т.к.

по условию в graphе конденсаций есть edge

, то из вершины

будет достижима не только вся компонента

,

но и вся компонента

. Это означает, что при запуске из вершины

обход в глубину пройдёт по всем

vertexм компонент

и

, а, значит, они станут потомками по отношению к

в дереве обхода в глубину, т.е.

для любой вершины

будет выполнено

, ч.т.д.

● Первой была достигнута компонента

. Опять же, в какой-то момент времени обход в глубину заходит в

некоторую вершину

, причём все остальные вершины компонент

и

не посещены. Поскольку по условию

в graphе конденсаций существовало edge

, то, вследствие ацикличности graphа конденсаций, не

существует обратного пути

, т.е. обход в глубину из вершины

не достигнет вершин

. Это означает, что

они будут посещены обходом в глубину позже, откуда и следует

, ч.т.д. Доказанная теорема является основой Algorithmа поиска компонент сильной связности. Из неё следует,

что любое edge

в graphе конденсаций идёт из компоненты с большей величиной

в компоненту с

меньшей величиной.

Если мы отсортируем все вершины

в порядке убывания времени Outputа

, то первой окажется

некоторая vertex

, принадлежащая "корневой" компоненте сильной связности, т.е. в которую не Inputит ни одно edge в graphе конденсаций. Теперь нам хотелось бы запустить такой обход из этой вершины

, который бы посетил только

эту компоненту сильной связности и не зашёл ни в какую другую; научившись это делать, мы сможем постепенно выделить все компоненты сильной связности: удалив из graphа вершины первой выделенной компоненты, мы

снова найдём среди оставшихся вершину с наибольшей величиной

, снова запустим из неё этот обход, и т.д. Чтобы научиться делать такой обход, рассмотрим транспонированный graph

, т.е. graph, полученный из

изменением направления каждого ребра на противоположное. Нетрудно понять, что в этом graphе будут те же компоненты сильной связности, что и в исходном graphе. Более того, graph конденсации

для него

будет равен транспонированному graphу конденсации исходного graphа

. Это означает, что теперь

из рассматриваемой нами "корневой" компоненты уже не будут Outputить рёбра в другие компоненты. Таким образом, чтобы обойти всю "корневую" компоненту сильной связности, содержащую некоторую вершину

, достаточно запустить обход из вершины

в graphе

. Этот обход посетит все вершины этой компоненты

сильной связности и только их. Как уже говорилось, дальше мы можем мысленно удалить эти вершины из graphа,

находить очередную вершину с максимальным значением

и запускать обход на транспонированном graphе

из неё, и т.д. Итак, мы построили следующий Algorithm выделения компонент сильной связности:

1 шаг. Запустить серию обходов в глубину graphа

, которая returns вершины в порядке увеличения времени

Outputа

, т.е. некоторый список

.

2 шаг. Построить транспонированный graph

. Запустить серию обходов в глубину/ширину этого graphа в

порядке, определяемом списком

(а именно, в обратном порядке, т.е. в порядке уменьшения времени Outputа). Каждое множество вершин, достигнутое в результате очередного запуска обхода, и будет очередной компонентой сильной связности.

Asymptotic complexity Algorithmа, очевидно, равна

, поскольку он представляет собой всего лишь два обхода

в глубину/ширину. Наконец, уместно отметить связь с понятием топологической сортировки. Во-первых, шаг 1 Algorithmа представляет собой не что иное, как топологическую сортировку graphа

(фактически именно это и

означает сортировка вершин по времени Outputа). Во-вторых, сама схема Algorithmа такова, что и компоненты сильной связности он генерирует в порядке уменьшения их времён Outputа, таким образом, он генерирует компоненты - вершины graphа конденсации в порядке топологической сортировки.

Implementation

vector < vector<int> > g, gr;

vector<char> used;

vector<int> order, component;

void dfs1 (int v) {

used[v] = true;

for (size_t i=0; i<g[v].size(); ++i)

if (!used[ g[v][i] ])

dfs1 (g[v][i]);

order.push_back (v);

}

void dfs2 (int v) {

used[v] = true;

component.push_back (v);

for (size_t i=0; i<gr[v].size(); ++i)

if (!used[ gr[v][i] ])

dfs2 (gr[v][i]);

}

int main() {

int n;

... чтение n ...

for (;;) {

int a, b;

... чтение очередного ребра (a,b) ...

g[a].push_back (b);

gr[b].push_back (a);

}

used.assign (n, false);

for (int i=0; i<n; ++i)

if (!used[i])

dfs1 (i);

used.assign (n, false);

for (int i=0; i<n; ++i) {

int v = order[n-1-i];

if (!used[v]) {

dfs2 (v);

... вывод очередной component ...

component.clear();

} } }

Здесь в

хранится сам graph, а

— транспонированный graph. Функция

выполняет обход в глубину на graphе

, функция

— на транспонированном

. Функция

заполняет список

vertexми в

порядке увеличения времени Outputа (фактически, делает топологическую сортировку). Функция

сохраняет

все достигнутые вершины в списке

, который после каждого запуска будет содержать

очередную компоненту сильной связности.

References

● Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Algorithmы: Построение и

анализ [2005]

● M. Sharir. A strong-connectivity algorithm and its applications in data-flow analysis [1979]

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    vector < List<int> > g, gr;
    List<char> used;
    List<int> order, component;
    void dfs1 (int v) {
            used[v] = true;
            for (size_t i=0; i<g[v].size(); ++i)
                    if (!used[ g[v][i] ])
                            dfs1 (g[v][i]);
            order.push_back (v);
    }
    void dfs2 (int v) {
            used[v] = true;
            component.push_back (v);
            for (size_t i=0; i<gr[v].size(); ++i)
                    if (!used[ gr[v][i] ])
                            dfs2 (gr[v][i]);
    }
    int main() {
            int n;
            ... чтение n ...
            for (;;) {
                    int a, b;
                    ... чтение очередного ребра (a,b) ...
                    g[a].push_back (b);
                    gr[b].push_back (a);
            }
            used.assign (n, false);
            for (int i=0; i<n; ++i)
                    if (!used[i])
                            dfs1 (i);
            used.assign (n, false);
            for (int i=0; i<n; ++i) {
                    int v = order[n-1-i];
                    if (!used[v]) {
                            dfs2 (v);
                            ... вывод очередной component ...
                            component.clear();
                    }
            }
    }
}

vector < vector<int> > g, gr;
vector<char> used;
vector<int> order, component;
void dfs1 (int v) {
        used[v] = true;
        for (size_t i=0; i<g[v].size(); ++i)
                if (!used[ g[v][i] ])
                        dfs1 (g[v][i]);
        order.push_back (v);
}
void dfs2 (int v) {
        used[v] = true;
        component.push_back (v);
        for (size_t i=0; i<gr[v].size(); ++i)
                if (!used[ gr[v][i] ])
                        dfs2 (gr[v][i]);
}
int main() {
        int n;
        ... чтение n ...
        for (;;) {
                int a, b;
                ... чтение очередного ребра (a,b) ...
                g[a].push_back (b);
                gr[b].push_back (a);
        }
        used.assign (n, false);
        for (int i=0; i<n; ++i)
                if (!used[i])
                        dfs1 (i);
        used.assign (n, false);
        for (int i=0; i<n; ++i) {
                int v = order[n-1-i];
                if (!used[v]) {
                        dfs2 (v);
                        ... вывод очередной component ...
                        component.clear();
                }
        }
}

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    vector < ArrayList<Integer> > g, gr;
    ArrayList<Character> used;
    ArrayList<Integer> order, component;
    void dfs1 (int v) {
            used[v] = true;
            for (size_t i=0; i<g[v].size(); ++i)
                    if (!used[ g[v][i] ])
                            dfs1 (g[v][i]);
            order.push_back (v);
    }
    void dfs2 (int v) {
            used[v] = true;
            component.push_back (v);
            for (size_t i=0; i<gr[v].size(); ++i)
                    if (!used[ gr[v][i] ])
                            dfs2 (gr[v][i]);
    }
    int main() {
            int n;
            ... чтение n ...
            for (;;) {
                    int a, b;
                    ... чтение очередного ребра (a,b) ...
                    g[a].push_back (b);
                    gr[b].push_back (a);
            }
            used.assign (n, false);
            for (int i=0; i<n; ++i)
                    if (!used[i])
                            dfs1 (i);
            used.assign (n, false);
            for (int i=0; i<n; ++i) {
                    int v = order[n-1-i];
                    if (!used[v]) {
                            dfs2 (v);
                            ... вывод очередной component ...
                            component.clear();
                    }
            }
    }
}