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

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

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

Дан ориентированный 그래프

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

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

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

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

количество вершин 그래프а, через

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

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

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

для

:

где символом

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

всех вершин 그래프а. Отсюда логично 정의 конденсации

как 그래프а, получаемого из данного

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

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

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

и

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

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

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

что

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

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

и

, что

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

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

вершины

и

, что

. Но т.к.

и

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

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

и

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

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

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

и

должны принадлежать одной компоненте сильной связности, т.е. получили противоречие, что и требовалось доказать. Описываемый ниже 알고리즘 выделяет в данном 그래프е все компоненты сильной связности. Построить по ним 그래프 конденсации не составит труда.

알고리즘

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

время

. На первом шаге 알고리즘а выполняется серия обходов в глубину, посещающая весь 그래프. Для этого мы проходимся по всем vertexм 그래프а и из каждой ещё не посещённой вершины вызываем обход в глубину. При

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

запомним время 출력а

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

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

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

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

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

из значений

для всех

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

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

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

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

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

для всех

.

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

и

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

ними есть edge

. Тогда

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

и

:

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

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

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

компоненты

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

и

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

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

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

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

,

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

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

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

vertexм компонент

и

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

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

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

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

, ч.т.д.

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

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

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

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

и

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

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

, то, вследствие ацикличности 그래프а конденсаций, не

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

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

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

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

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

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

что любое edge

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

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

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

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

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

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

некоторая vertex

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

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

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

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

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

, т.е. 그래프, полученный из

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

для него

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

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

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

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

в 그래프е

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

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

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

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

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

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

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

출력а

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

.

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

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

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

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

Asymptotic complexity 알고리즘а, очевидно, равна

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

в глубину/ширину. Наконец, уместно отметить связь с понятием топологической сортировки. Во-первых, шаг 1 알고리즘а представляет собой не что иное, как топологическую сортировку 그래프а

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

означает сортировка вершин по времени 출력а). Во-вторых, сама схема 알고리즘а такова, что и компоненты сильной связности он генерирует в порядке уменьшения их времён 출력а, таким образом, он генерирует компоненты - вершины 그래프а конденсации в порядке топологической сортировки.

구현

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();

} } }

Здесь в

хранится сам 그래프, а

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

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

, функция

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

. Функция

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

vertexми в

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

сохраняет

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

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

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

References

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

анализ [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();
                    }
            }
    }
}