Алгоритм сильных компонент на основе пути

В теории графов ориентированного сильно связные компоненты можно графа найти с помощью алгоритма, который использует поиск в глубину в сочетании с двумя стеками : один для отслеживания вершин в текущем компоненте, а второй для отслеживания текущего компонента. путь поиска. Версии этого алгоритма были предложены Purdom (1970) , Munro (1971) , Dijkstra (1976) , Cheriyan & Mehlhorn (1996) и Gabow (2000) ; из них версия Дейкстры была первой, достигшей линейного времени .

Описание

Алгоритм выполняет поиск в глубину заданного графа G , сохраняя при этом два стека S и P (в дополнение к обычному стеку вызовов для рекурсивной функции).Стек S содержит все вершины, которые еще не были назначены сильно связному компоненту, в том порядке, в котором поиск в глубину достигает вершин.Стек P содержит вершины, принадлежность которых еще не была определена к разным сильно связанным друг с другом компонентам. Он также использует счетчик C количества достигнутых на данный момент вершин, который используется для вычисления номеров предварительного порядка вершин.

Когда поиск в глубину достигает вершины v , алгоритм выполняет следующие шаги:

1. Установите номер предварительного заказа v на C и C. увеличьте
2. Нажмите v на S а также на P. ,
3. Для каждого ребра от v до соседней вершины w :
   • Если предварительный номер w еще не назначен (ребро является ребром дерева ), выполните рекурсивный поиск w ;
   • В противном случае, если w еще не присвоен сильно связному компоненту (ребро является прямым/обратным/перекрестным ребром):
     • Повторно извлекайте вершины из P до тех пор, пока верхний элемент P не будет иметь номер предварительного порядка, меньший или равный номеру предварительного порядка w .
4. Если v является верхним элементом P :
   • Извлекайте вершины из S до тех пор, пока v не будет вытолкнуто, и назначьте вытолкнутые вершины новому компоненту.
   • Поп v из P. ​

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

Связанные алгоритмы

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

Ссылки

• Чериян, Дж.; Мельхорн, К. (1996), «Алгоритмы для плотных графов и сетей на компьютере с произвольным доступом», Algorithmica , 15 (6): 521–549, doi : 10.1007/BF01940880 , S2CID   8930091 .
• Дейкстра, Эдсгер (1976), Дисциплина программирования , Нью-Джерси: Прентис Холл, гл. 25 .
• Габоу, Гарольд Н. (2000), «Поиск в глубину сильных и двусвязных компонентов на основе путей» (PDF) , Information Processing Letters , 74 (3–4): 107–114, doi : 10.1016/S0020-0190( 00)00051-Х , МР   1761551 .
• Манро, Ян (1971), «Эффективное определение транзитивного замыкания ориентированного графа», Information Processing Letters , 1 (2): 56–58, doi : 10.1016/0020-0190(71)90006-8 .
• Пурдом, П. младший (1970), «Алгоритм транзитивного замыкания» , BIT , 10 : 76–94, doi : 10.1007/bf01940892 , S2CID   20818200 .
• Седжвик, Р. (2004), «19.8 Сильные компоненты в орграфах», Алгоритмы на Java, Часть 5 – Алгоритмы графов (3-е изд.), Кембридж, Массачусетс: Аддисон-Уэсли, стр. 205–216 .