Алгоритм Тарьяна поиска компонент двусвязности: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) Общее описание алгоритма |
Daryin (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Алгоритм Тарьяна'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> находит [[Связность в графах|компоненты | '''Алгоритм Тарьяна'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> находит [[Связность в графах|компоненты двусвязности]] неориентированного графа в процессе [[Поиск в глубину (DFS)|поиска в глубину]]) за время <math>O(m)</math>. | ||
=== Математическое описание === | === Математическое описание === | ||
Версия от 20:53, 7 июня 2015
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Тарьяна[1] находит компоненты двусвязности неориентированного графа в процессе поиска в глубину) за время [math]\displaystyle{ O(m) }[/math].
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Последовательная сложность алгоритма Тарьяна составляет [math]\displaystyle{ O(m) }[/math], так как в процессе поиска в ширину выполняется ограниченное количество операций для каждой вершины и каждого ребра.
Информационный граф
Описание ресурса параллелизма алгоритма
Возможности параллелизации алгоритма Тарьяна сильно ограничены, поскольку он основан на поиске в глубину. Параллельный алгоритмом Тарьяна-Вишкина[2] основан на тех же свойствах графа и может использовать любое остовное дерево.