2 Алгоритм Косарайю

2.1 Теоретическое обоснование алгоритма

Поиск компонент сильной связности стал возможен благодаря поиску в глубину на ориентированном графе. Описываемый здесь алгоритм был предложен независимо Косарайю в 1979 году.

Чтобы найти области сильной связности, сначала выполняется поиск в глубину на обращении исходного графа, вычисляя порядок выхода из вершин. Затем мы используем обращение этого порядка, чтобы выполнить поиск в глубину на исходном графе (в очередной раз берём вершину с максимальным номером, полученным при обратном проходе). Деревья в лесе DFS, которые выбираются в результате, представляют собой сильные компоненты. [4]

Этот алгоритм, работает на двух сериях поисков в глубину(допустим обход в ширину), и потому выполняется за время O(n + m)

На первом шаге мы проходим по всем вершинам графа и из каждой не посещённой вершины вызываем поиск в глубину. При этом для каждой вершины v запомним время выхода tout[v]. Эти времена выхода играют ключевую роль в алгоритме, и эта роль выражена в изложенной ниже теореме.

Шаг 1 алгоритма представляет собой не что иное, как топологическую сортировку графа G (фактически именно это и означает сортировка вершин по времени выхода)

Сначала введём обозначение: время выхода tout[C] из компоненты C

сильной связности определим как максимальное значение из tout[v] для всех v 2 C. Время входа в каждую вершину – tin[v], и определим время входа tin[C] для каждой компоненты сильной связности как минимальное значение из tin[v] для всех v 2 C.

Теорема. Пусть C и C0 — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро (C; C0). Тогда tout[C] > tout[C0]. [5]

При доказательстве возможны два различных случая в зависимости от того, в какую из компонент первой зайдёт обход в глубину, то есть в зависимости от соотношения между tin[C] и tin[C0]:

Допустим, первой была достигнута компонента C. Это означает, что в какой-то момент времени обход в глубину заходит в некоторую вершину v

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

7

посещены. Но, так как по условию в графе конденсаций есть ребро (C; C0), то из вершины v будет достижима не только вся компонента C, но и вся компонента C0. Это означает, что при запуске из вершины v обход в глубину посетит все вершины компонент C и C0, а, значит, они станут потомками по отношению к v в дереве обхода в глубину, то есть для любой вершины u

2 C [ C0, u 6= v будет выполнено tout[v] > tout[u].

Предположим, что первой была достигнута компонента C0.Получается, в какой-то момент времени обход в глубину заходит в некоторую вершину v 2 C0, причём все остальные вершины компонент C и C0 не посещены. Поскольку по условию в графе конденсаций существовало ребро (C; C0), то, вследствие ацикличности графа конденсаций, не существует обратного пути

C0 67!C,то есть обход в глубину из вершины v не достигнет вершин C. Это означает, что они будут посещены обходом в глубину позже, откуда и следует tout[C] > tout[C0].

Доказанная теорема является основой алгоритма поиска компонент сильной связности. Из неё следует, что любое ребро (C; C0) в графе конденсаций выходит из компоненты с большей величиной tout в компоненту с меньшей величиной.

Если мы отсортируем все вершины v 2 V в порядке убывания времени выхода tout[v], то первой окажется некоторая вершина u, принадлежащая "корневой"компоненте сильной связности,то есть в которую не входит ни одно ребро в графе конденсаций. Теперь нам хотелось бы запустить такой обход из этой вершины u, который бы посетил только эту компоненту сильной связности и не оказался в другой; научившись это делать, мы сможем постепенно выделить все компоненты сильной связности: удалив из графа вершины первой выделенной компоненты, мы снова найдём среди оставшихся вершину с наибольшей величиной tout и снова запустим из неё обход, и так далее. [6]

Чтобы научиться делать такой обход, рассмотрим транспонированный граф GT , т.е. граф, полученный из G инвертированием. Инвертированием ориентированного графа назовем процедуру, в ходе которой поменяем направление каждого ребра на противоположное. Понятно, что в этом графе будут те же компоненты сильной связности, что и в исходном графе. Более того, граф конденсации (GT )SCC для него будет равен транспонированному графу конденсации исходного графа GSCC. Это означает, что теперь из рассматри-

8

ваемой нами "корневой"компоненты уже не будут выходить рёбра в другие компоненты.

Таким образом, чтобы обойти всю "корневую"компоненту сильной связности, содержащую некоторую вершину v, достаточно запустить обход из вершины v в графе GT . Этот обход посетит все вершины этой компоненты сильной связности и только их. Как уже говорилось, дальше мы можем мысленно удалить эти вершины из графа, находить очередную вершину с максимальным значением tout[v] и запускать обход на транспонированном графе из неё, и так далее.

Так выглядит алгоритм выделения компонент сильной связности:

—Отсортировать граф топологически, то есть:

–выполнить DFS, сохраняя время выхода для каждой вершины;

–отсортировать вершины в порядке убывания по времени выхода ? это и получится топологически отсортированный граф.

—Транспонировать граф.

—Обойти граф с помощью DFS или BFS, выбирая вершины согласно топологическому порядку.

–все достижимые вершины добавляются в список, соответствующий текущей компоненте связности;

–как только встретится вершина, из которой не существует пути в еще не посещенную вершину, нужно добавить новую компоненту связности и сохранять последующие вершины там.

2.2 Асимптотика

Для того, чтобы инвертировать все ребра в графе, представленном в виде списка потребуется O(V + E) действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования. [3] Количество ребер в инвертированном равно количеству ребер в изначальном графе, поэтому поиск в глубину будет работать за O(V + E) Поиск в глубину в исходном графе выполняется за O(V + E). В итоге получаем, что время работы алгоритма O(V + E).

2.3 Реализация

1 vector < vector<int> > g, gr;

2 vector<char> used;

9

3 vector<int> order, component;

4

5 void dfs1 (int v) {

6used[v] = true;

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

10order.push_back (v);

11}

12void dfs2 (int v) {

13used[v] = true;

14component.push_back (v);

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

10