Алгоритм Тарьяна поиска «мостов» в графе

Свойства и структура алгоритма

Общее описание алгоритма

Алгоритм Тарьяна находит мосты в неориентированном графе за время [math]\displaystyle{ O(m) }[/math].

Математическое описание алгоритма

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

Пусть задан ориентированный граф [math]\displaystyle{ G=(V,E) }[/math] с вершинами [math]\displaystyle{ V= (v_1,v_2,...,v_n) }[/math] и рёбрами [math]\displaystyle{ E=(e_1,e_2,...,e_m) }[/math].

Путём между вершинами [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] называется последовательность рёбер [math]\displaystyle{ \pi_{uv}=(e_1,...,e_k) }[/math], начинающаяся в вершине [math]\displaystyle{ u }[/math] и заканчивающаяся в вершине [math]\displaystyle{ v }[/math], так что началом каждого следующего ребра служит конец предыдущего.

Если существует такой путь [math]\displaystyle{ \pi_{uv} }[/math], то вершина [math]\displaystyle{ v }[/math] достижима из вершины [math]\displaystyle{ u }[/math]. Считается, что от вершины [math]\displaystyle{ u }[/math] к самой себе ведёт пустой путь [math]\displaystyle{ \pi_{uu} }[/math], то есть каждая вершина достижима из самой себя. Непустой путь [math]\displaystyle{ \pi_{uu} }[/math] называется циклом (замкнутым обходом).

Ориентированный граф называется сильно связным, если всякая его вершина [math]\displaystyle{ v }[/math] достижима из любой другой его вершины [math]\displaystyle{ u }[/math]. Компонентой сильной связности ориентированного графа называется любой максимальный по включению сильно связный подграф.

Последовательная сложность алгоритма

Последовательная сложность алгоритма составляет [math]\displaystyle{ O(m) }[/math].

Ресурс параллелизма алгоритма

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

Параллельный алгоритм Тарьяна-Вишкина основан на аналогичных вычислениях и может быть адаптирован для поиска мостов.