Алгоритм Косараджуса - Kosarajus algorithm - Wikipedia

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

Алгоритм

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

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

1. Для каждой вершины ты графика, отметьте ты как не посещенный. Позволять L быть пустым.
2. Для каждой вершины ты графика сделать Посетите (ты), где Посетите (ты) - это рекурсивная подпрограмма:

   Если ты не посещается тогда:

   1. отметка ты как посетил.
   2. Для каждого ближнего v из ты, посетите (v).
   3. Подготовить ты к L.

   Иначе ничего не делать.

3. Для каждого элемента ты из L по порядку, сделайте Assign (ты,ты) где Assign (ты,корень) - это рекурсивная подпрограмма:

   Если ты не был назначен компоненту, тогда:

   1. Назначать ты как принадлежащий компоненту, корень которого корень.
   2. Для каждого соседа v из ты, назначить (v,корень).

   Иначе ничего не делать.

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

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

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

${\displaystyle B(u)\cap F(u)=B(u)\setminus (B(u)\setminus F(u))=B(u)\setminus P(u)}$.

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

Сложность

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

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

Рекомендации

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

внешняя ссылка

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