Алгоритм сильных компонентов на основе путей - Википедия - Path-based strong component algorithm

В теория графов, то компоненты сильной связности из ориентированный граф можно найти с помощью алгоритма, который использует поиск в глубину в сочетании с двумя стеки, один для отслеживания вершин в текущем компоненте, а второй для отслеживания текущего пути поиска.[1] Варианты этого алгоритма были предложены Purdom (1970), Манро (1971), Дейкстра (1976), Чериян и Мельхорн (1996), и Габоу (2000); из них версия Дейкстры была первой, линейное время.[2]

Описание

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

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

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

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

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

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

Примечания

  1. ^ Седжвик (2004).
  2. ^ История DFS на основе путей для сильных компонентов, Гарольд Н. Габоу, дата обращения 24 апреля 2012 г.

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

  • Cheriyan, J .; Мельхорн, К. (1996), «Алгоритмы для плотных графов и сетей на компьютере с произвольным доступом», Алгоритмика, 15 (6): 521–549, Дои:10.1007 / BF01940880, S2CID  8930091.
  • Дейкстра, Эдсгер (1976), Дисциплина программирования, Нью-Джерси: Prentice Hall, Ch. 25.
  • Габоу, Гарольд Н. (2000), «Поиск в глубину на основе пути для сильных и двусвязных компонентов», Письма об обработке информации, 74 (3–4): 107–114, Дои:10.1016 / S0020-0190 (00) 00051-X, МИСТЕР  1761551.
  • Манро, Ян (1971), "Эффективное определение транзитивного замыкания ориентированного графа", Письма об обработке информации, 1 (2): 56–58, Дои:10.1016/0020-0190(71)90006-8.
  • Пурдом, П., младший (1970), «Алгоритм транзитивного замыкания», КУСОЧЕК, 10: 76–94, Дои:10.1007 / bf01940892, S2CID  20818200.
  • Седжвик, Р. (2004), "19,8 сильных компонентов в диграфах", Алгоритмы в Java, часть 5 - Графические алгоритмы (3-е изд.), Cambridge MA: Addison-Wesley, pp. 205–216.