Алгоритм Косараджу

В информатике алгоритм Косараджу-Шарира (также известный как алгоритм Косараджу ) представляет собой с линейным временем алгоритм для поиска сильно связанных компонентов графа ориентированного . Ахо , Хопкрофт и Уллман приписывают это С. Рао Косараджу и Михе Шариру . Косараджу предложил его в 1978 году, но не опубликовал, в то время как Шарир независимо обнаружил его и опубликовал в 1981 году. Он использует тот факт, что транспонированный граф (тот же граф с обратным направлением каждого ребра) имеет точно такую же сильно связанную структуру. компоненты как исходный граф.

Алгоритм

Примитивные операции с графом, которые использует алгоритм, заключаются в перечислении вершин графа, сохранении данных для каждой вершины (если не в самой структуре данных графа, то в некоторой таблице, которая может использовать вершины в качестве индексов), для перечисления внешних соседей. вершины (обход ребер в прямом направлении) и перечисление внутренних соседей вершины (обход ребер в обратном направлении); однако последнее можно обойтись ценой построения представления транспонированного графа на этапе прямого обхода. Единственная дополнительная структура данных, необходимая алгоритму, — это упорядоченный список $L$ вершин графа, который будет расти и содержать каждую вершину один раз.

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

Для каждой вершины $u$ графа отметьте $ее$ как непосещенную. Пусть $L$ пусто.
Для каждой вершины u графа выполните Visit(u), где Visit(u) это рекурсивная подпрограмма:
Если вас не посетили, то:
1. Отметить $вас$ как посещенный.
2. Для каждого внешнего соседа $v$ из $u$ выполните Visit(v).
3. Добавьте $u$ к $L$ .
В противном случае ничего не делайте.
Для каждого элемента u из L по порядку выполните Assign(u,u) где Assign(u,root) это рекурсивная подпрограмма:
Если вы не были назначены компоненту, то:
1. Назначьте $u$ как принадлежащий компоненту, корнем которого является $root$ .
2. Для каждого соседа $v$ из $u$ выполните Assign(v,root).
В противном случае ничего не делайте.

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

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

Это означает, что каждый элемент $n$ списка может соответствовать блоку $L[i n -1 : in n]$ , где блок состоит из всех вершин, достижимых из вершины $n,$ используя только внешние ребра в каждом узле в путь. Важно отметить, что ни одна вершина в блоке, начинающемся с $n,$ начинающимся с некоторой вершины справа от него, т. е. блоки, соответствующие вершинам $in n, in +1 не имеет внутренней связи ни с одним из блоков ,, \dots N$ в список. Это так, потому что в противном случае вершина, имеющая внутреннюю ссылку (скажем, из блока, начинающегося с $n' \geq in n +1$ ), уже была бы посещена и добавлена к $L$ в блоке из $n'$ , что является противоречием. С другой стороны, вершины в блоке, начинающиеся с $n,$ могут иметь ребра, указывающие на блоки, начинающиеся с некоторой вершины в ${i n, i n +1, \dots N}.$

Шаг 3 алгоритма, начиная с $L[0]$ , назначает всем вершинам, которые указывают на него, тот же компонент, что и $L[0]$ . Обратите внимание, что эти вершины могут находиться только в блоке, начинающемся с $L[0],$ поскольку более высокие блоки не могут иметь ссылки, указывающие на вершины в блоке $L[0]$ . Пусть набор всех вершин, указывающих на $L[0],$ равен $In(L[0])$ . Впоследствии все вершины, указывающие на эти вершины, $In(In(L[0]))$ тоже добавляются, и так далее, пока больше вершин нельзя будет добавить.

Существует путь к $L[0]$ из всех вершин, добавленных в компонент, содержащий $L[0]$ . И существует путь ко всем вершинам, добавленным из $L[0]$ , поскольку все они лежат в блоке, начинающемся с $L[0]$ (который содержит все вершины, достижимые из $L[0]$ после внешних ребер на каждом шаге пути) . Следовательно, все они образуют единую сильно связную компоненту. Более того, не остается ни одной вершины, потому что для того, чтобы попасть в этот сильно связный компонент, вершина должна быть достижима из $L[0]$ и должна иметь возможность достичь $L[0]$ . Все вершины, которые могут достичь $L[0]$ , если таковые имеются, лежат только в первом блоке, и все вершины в первом блоке достижимы из $L[0]$ . Таким образом, алгоритм выбирает все вершины компонента связности $L[0]$ .

Когда мы достигаем вершины $v = L[i]$ в цикле шага 3 и $v$ не присвоен ни одному компоненту, мы можем быть уверены, что все вершины слева создали свои связные компоненты; что $v$ не принадлежит ни одному из этих компонентов; что $v$ не указывает ни на одну из вершин слева от него. Кроме того, поскольку не существует ребра от блоков более высокого уровня к $блоку v$ , доказательство остается прежним.

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

Алгоритм можно понимать как идентификацию сильной компоненты вершины $u$ как набора вершин, достижимых из $u$ путем обхода вперед и назад. Записывая $F (u)$ для набора вершин, достижимых из $u$ путем прямого обхода, $B (u)$ для набора вершин, достижимых из $u$ путем обратного обхода, и $P (u)$ для набора вершин, которые появляются строго перед $u$ на список $L$ после фазы 2 алгоритма, сильный компонент, содержащий вершину $u,$ назначенную корнем, равен

B(u)\cap F(u)=B(u)\setminus (B(u)\setminus F(u))=B(u)\setminus P(u).

Пересечение множеств требует больших вычислительных затрат, но логически эквивалентно двойной разнице множеств , и поскольку ⁠ $B(u)\setminus F(u)\subseteq P(u)$ ⁠ становится достаточным проверить, был ли вновь встретившийся элемент $B (u)$ уже присвоен компоненту или нет.

Сложность

При условии, что граф описывается с использованием списка смежности , алгоритм Косараджу выполняет два полных обхода графа и, таким образом, работает за Θ(V+E) (линейное) время, что асимптотически оптимально , поскольку существует соответствующая нижняя граница (любой алгоритм должен проверять все вершины и ребра). Это концептуально самый простой эффективный алгоритм, но на практике он не так эффективен, как алгоритм сильно связанных компонентов Тарьяна и алгоритм сильных компонентов на основе путей , которые выполняют только один обход графа.

Если граф представлен в виде матрицы смежности , алгоритм требует Ο(V ²) время.

Ссылки

Альфред В. Ахо , Джон Э. Хопкрофт , Джеффри Д. Ульман . Структуры данных и алгоритмы . Аддисон-Уэсли, 1983 год.
Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест , Клиффорд Стейн . Введение в алгоритмы , 3-е издание. Массачусетский технологический институт Пресс, 2009. ISBN 0-262-03384-4 .
Миша Шарир . Алгоритм сильной связности и его применение к анализу потоков данных. Компьютеры и математика с приложениями 7 (1): 67–72, 1981.

Внешние ссылки

Хорошая математика, плохая математика: вычисление сильно связанных компонентов