Алгоритм поиска компонент сильной связности с двумя стеками (Glikjnmb hknvtg tkbhkuyum vnl,ukw vfx[ukvmn v ;frbx vmytgbn)

Перейти к навигации Перейти к поиску

Основанный на поиске путей алгоритм нахождения компонент сильной связности ориентированного графа — это алгоритм, использующий поиск в глубину в комбинации с двумя стеками, один хранит вершины текущей компоненты, а второй хранит текущий путь[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 Архивная копия от 20 мая 2017 на Wayback Machine, 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.
Источник — https://ru.wikipedia.org/w/index.php?title=Алгоритм_поиска_компонент_сильной_связности_с_двумя_стеками&oldid=122890706