Алгоритм Тарьяна поиска компонент двусвязности
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Тарьяна[1] находит компоненты двусвязности и шарниры неориентированного графа в процессе поиска в глубину за время [math]\displaystyle{ O(m) }[/math].
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Последовательная сложность алгоритма Тарьяна составляет [math]\displaystyle{ O(m) }[/math], так как в процессе поиска в ширину выполняется ограниченное количество операций для каждой вершины и каждого ребра.
Информационный граф
Ресурс параллелизма алгоритма
Возможности параллелизации алгоритма Тарьяна сильно ограничены, поскольку он основан на поиске в глубину. Параллельный алгоритмом Тарьяна-Вишкина[2] основан на тех же свойствах графа и может использовать любое остовное дерево.
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- C++: Boost Graph Library (функция
biconnected_components). - Python: NetworkX (функция
biconnected_components). - Java: JGraphT (класс
BiconnectivityInspector).