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

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

Версия от 14:43, 11 июня 2015

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

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

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

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

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

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

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

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

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

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

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

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

Описание входных и выходных данных

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

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

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

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

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

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

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

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

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

Boost Graph Library (функция strong_components).

Литература

↑ 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]

@@ Строка 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>.
 === Математическое описание ===
 === Вычислительное ядро алгоритма ===