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

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

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

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

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

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

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

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

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

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

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

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

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

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

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