В информатике алгоритм Косараджу-Шарира (также известный как алгоритм Косараджу ) представляет собой алгоритм с линейным временем для поиска сильно связанных компонентов ориентированного графа . Ахо , Хопкрофт и Уллман приписывают это С. Рао Косараджу и Михе Шариру . Косараджу предложил его в 1978 году, но не опубликовал, в то время как Шарир независимо обнаружил его и опубликовал в 1981 году. Он использует тот факт, что транспонированный граф (тот же граф с обратным направлением каждого ребра) имеет точно такую же сильно связную структуру. компоненты как исходный граф.
Примитивные операции с графом, которые использует алгоритм, заключаются в перечислении вершин графа, сохранении данных для каждой вершины (если не в самой структуре данных графа, то в некоторой таблице, которая может использовать вершины в качестве индексов), для перечисления внешних соседей. вершины (обход ребер в прямом направлении) и перечисление внутренних соседей вершины (обход ребер в обратном направлении); однако последнего можно обойтись ценой построения представления транспонированного графа на этапе прямого обхода. Единственная дополнительная структура данных, необходимая алгоритму, — это упорядоченный список L вершин графа, который будет расти и содержать каждую вершину один раз.
Если сильные компоненты должны быть представлены путем назначения отдельной корневой вершины для каждого компонента и присвоения каждой вершине корневой вершины ее компонента, то алгоритм Косараджу можно сформулировать следующим образом.
Visit(u), где Visit(u)– рекурсивная подпрограмма:Visit(v).Assign(u,u)is Assign(u,root)рекурсивная подпрограмма: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 , … N в список. Это так, потому что в противном случае вершина, имеющая внутреннюю ссылку (скажем, из блока, начинающегося с n' ≥ in n +1 ), уже была бы посещена и добавлена к L в блоке из n' , что является противоречием. С другой стороны, вершины в блоке, начинающиеся с n , могут иметь ребра, указывающие на блоки, начинающиеся с некоторой вершины в { i n , i n +1 , … 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 ) компоненту или нет.
При условии, что граф описывается с использованием списка смежности , алгоритм Косараджу выполняет два полных обхода графа и, таким образом, работает за Θ(V+E) (линейное) время, что асимптотически оптимально, поскольку существует соответствующая нижняя граница (любой алгоритм должен проверять все вершины и ребра). Это концептуально самый простой эффективный алгоритм, но на практике он не так эффективен, как алгоритм сильно связанных компонентов Тарьяна и алгоритм сильных компонентов на основе путей , которые выполняют только один обход графа.
Если граф представлен в виде матрицы смежности , алгоритму требуется время 0( V2 ) .
