Алгоритм Тарьяна поиска компонент сильной связности

Материал из Алговики
Перейти к навигации Перейти к поиску

Содержание

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

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

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

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

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

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

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

1.7 Информационный граф

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

Алгоритм основан на поиске в глубину и поэтому возможности его параллелизации сильно ограничены.

1.9 Входные и выходные данные алгоритма

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

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. ↑ Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
Источник — https://algowiki-project.org/w/ru/index.php?title=Алгоритм_Тарьяна_поиска_компонент_сильной_связности&oldid=2278