Русская Википедия:Алгоритм поиска компонент сильной связности с двумя стеками
Основанный на поиске путей алгоритм нахождения компонент сильной связности ориентированного графа — это алгоритм, использующий поиск в глубину в комбинации с двумя стеками, один хранит вершины текущей компоненты, а второй хранит текущий путьШаблон:Sfn. Версии этого алгоритма предложили ПёрдомШаблон:Sfn, МанроШаблон:Sfn, ДейкстраШаблон:Sfn, Чериян, МелхорнШаблон:Sfn и ГабовШаблон:Sfn. Из них версия Дейкстры была первой, работающей за линейное время[1]
Описание
Алгоритм осуществляет поиск в глубину на данном графе G, поддерживая два стека, S и P (вдобавок к нормальному стеку вызовов для рекурсивных функций). Стек S содержит все вершины, которые ещё не назначены компоненте сильной связности в порядке, в котором поиск в глубину достигает вершины. Стек P содержит вершины, для которых ещё не определено, какой компоненте связности вершина принадлежит. Алгоритм также использует счётчик C достигнутых вершин, который используется для вычисления предпорядка вершин.
Когда поиск в глубину достигает вершину v, алгоритм осуществляет следующие шаги:
- Номер предпорядка вершины v устанавливается в C, а затем C увеличивается.
- Вершина v помещается в S и в P.
- Для каждой дуги из v в соседнюю вершину w:
- Если номер предпорядка вершины w ещё не назначен, рекурсивно просматриваем w;
- В противном случае, если вершина w ещё не назначена компоненте сильной связности:
- Последовательно выталкиваем вершины из P, пока элемент на вершине стека P не будет иметь номер предпорядка, меньший либо равный номера предпорядка вершины w.
- Если вершина v находится на вершине стека P:
- Выталкиваем вершины из S, пока не будет вытолкнута вершина v, и назначаем вытолкнутые вершины новой компоненте.
- Выталкиваем v из P.
Алгоритм состоит из цикла по вершинам графа, вызывая рекурсивный поиск на каждой вершине, которой не назначен номер предпорядка.
Связанные алгоритмы
Подобно описанному алгоритму, алгоритм Тарьяна поиска компонент сильной связности также использует поиск в глубину вместе со стеком для хранения вершин, которые ещё не назначены какой-либо компоненте сильной связности, и алгоритм переносит эти вершины в новую компоненту, когда алгоритм кончает расширять последнюю вершину компоненты. Однако вместо стека P алгоритм Тарьяна использует индексированный вершинами массив чисел предпорядка, назначенных в порядке посещения вершин при поиске в глубину. Массив предпорядков используется для отслеживания, когда следует образовать новую компоненту.
Примечания
Литература
- ↑ History of Path-based DFS for Strong Components Шаблон:Wayback, Harold N. Gabow, accessed 2012-04-24.
