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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 2: Строка 2:
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
Алгоритм Тарьяна<ref name=DFS>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>.
+
'''Алгоритм Тарьяна'''<ref name=DFS>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>.
+
 
 
=== Математическое описание ===
 
=== Математическое описание ===
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===

Версия 17:43, 11 июня 2015

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.3 Возможные способы и особенности реализации параллельного алгоритма

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

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.