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