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

[непроверенная версия]

[досмотренная версия]

Текущая версия от 11:46, 6 июля 2022

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты прогонов

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

Литература

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

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

[1]

@@ Строка 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>.
-=== Математическое описание ===
+=== Математическое описание алгоритма ===
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===
-=== Описание схемы реализации последовательного алгоритма ===
+=== Схема реализации последовательного алгоритма ===
 === Последовательная сложность алгоритма ===
@@ Строка 13: / Строка 15: @@
 === Информационный граф ===
-=== Описание ресурса параллелизма алгоритма ===
+=== Ресурс параллелизма алгоритма ===
 Алгоритм основан на [[Поиск в глубину (DFS)|поиске в глубину]] и поэтому возможности его параллелизации сильно ограничены.
-=== Описание входных и выходных данных ===
+=== Входные и выходные данные алгоритма ===
-=== Свойства алгоритма===
+=== Свойства алгоритма ===
-== Программная реализация алгоритмов ==
+== Программная реализация алгоритма ==
 === Особенности реализации последовательного алгоритма ===
-=== Описание локальности данных и вычислений ===
+=== Возможные способы и особенности параллельной реализации алгоритма ===
-=== Возможные способы и особенности реализации параллельного алгоритма ===
+=== Результаты прогонов ===
-=== Масштабируемость алгоритма и его реализации ===
-=== Динамические характеристики и эффективность реализации алгоритма ===
 === Выводы для классов архитектур ===
-=== Существующие реализации алгоритма ===
-* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/strong_components.html strong_components]</code>).
-* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/StronglyConnectedComponents.html StronglyConnectedComponents]</code>).
-* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/StrongConnectivityInspector.html StrongConnectivityInspector]</code>).
-* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.components.strongly_connected.strongly_connected_components.html strongly_connected_components]</code>).
-* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/properties.html#networkit.properties.StronglyConnectedComponents networkit.properties.StronglyConnectedComponents]</code>).
 == Литература ==
 <references />
+[[Категория:Начатые статьи]]
+[[en:Tarjan's strongly connected components algorithm]]