Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
 
(не показано 8 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Свойства и структура алгоритмов ==
+
{{level-a}}
 +
 
 +
== Свойства и структура алгоритма ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
 
'''Алгоритм Тарьяна'''<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>.
  
=== Математическое описание ===
+
=== Математическое описание алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
  
Строка 13: Строка 15:
  
 
=== Информационный граф ===
 
=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
  
 
Алгоритм основан на [[Поиск в глубину (DFS)|поиске в глубину]] и поэтому возможности его параллелизации сильно ограничены.
 
Алгоритм основан на [[Поиск в глубину (DFS)|поиске в глубину]] и поэтому возможности его параллелизации сильно ограничены.
  
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма===
+
=== Свойства алгоритма ===
== Программная реализация алгоритмов ==
+
 
 +
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
=== Результаты прогонов ===
=== Масштабируемость алгоритма и его реализации ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
 
 
* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/strong_components.html strong_components]</code>).
 
  
 
== Литература ==
 
== Литература ==
  
 
<references />
 
<references />
 +
 +
[[Категория:Начатые статьи]]
 +
 +
[[en:Tarjan's strongly connected components algorithm]]

Текущая версия на 14:46, 6 июля 2022


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 Выводы для классов архитектур

3 Литература

  1. Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.