Алгоритм поиска компонент сильной связности с двумя стеками

Основанный на поиске путей алгоритм нахождения компонент сильной связности ориентированного графа — это алгоритм, использующий поиск в глубину в комбинации с двумя стеками, один хранит вершины текущей компоненты, а второй хранит текущий путь[1]. Версии этого алгоритма предложили Пёрдом[2], Манро[3], Дейкстра[4], Чериян, Мелхорн[5] и Габов[6]. Из них версия Дейкстры была первой, работающей за линейное время[7]

Описание

Алгоритм осуществляет поиск в глубину на данном графе 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 алгоритм Тарьяна использует индексированный вершинами массив чисел предпорядка, назначенных в порядке посещения вершин при поиске в глубину. Массив предпорядков используется для отслеживания, когда следует образовать новую компоненту.

Примечания
  1. Sedgewick, 2004.
  2. Purdom, 1970.
  3. Munro, 1971.
  4. Dijkstra, 1976.
  5. Cheriyan, Mehlhorn, 1996.
  6. Gabow, 2000.
  7. History of Path-based DFS for Strong Components, Harold N. Gabow, accessed 2012-04-24.

Литература
  • Cheriyan J., Mehlhorn K. Algorithms for dense graphs and networks on the random access computer // Algorithmica. — 1996. — Т. 15. — С. 521–549. — doi:10.1007/BF01940880.
  • Edsger Dijkstra. Ch. 25 // A Discipline of Programming. — NJ: Prentice Hall, 1976.
    • Э. Дейкстра. Дисциплина программирования. — «Мир», 1978. — (Математическое обеспечение ЭВМ).
  • Harold N. Gabow. Path-based depth-first search for strong and biconnected components // Information Processing Letters. — 2000. — Т. 74, вып. 3-4. — С. 107–114. — doi:10.1016/S0020-0190(00)00051-X.
  • Ian Munro. Efficient determination of the transitive closure of a directed graph // Information Processing Letters. — 1971. — Т. 1. — С. 56–58. — doi:10.1016/0020-0190(71)90006-8.
  • Purdom P., Jr. A transitive closure algorithm // BIT. — 1970. — Т. 10. — С. 76–94. — doi:10.1007/bf01940892.
  • Sedgewick R. 19.8 Strong Components in Digraphs // Algorithms in Java, Part 5 – Graph Algorithms. — 3rd. — Cambridge MA: Addison-Wesley, 2004. — С. 205–216.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.