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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
 
(не показано 9 промежуточных версий 3 участников)
Строка 1: Строка 1:
== Свойства и структура алгоритмов ==
+
{{level-a}}
 +
 
 +
== Свойства и структура алгоритма ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
'''Алгоритм Тарьяна'''<ref>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>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>.
 +
 
 +
Процесс поиска в глубину является существенно последовательным (inherently sequential) и практически не параллелизуется. Вместе с тем, алгоритм Тарьяна по-видимому является максимально возможно эффективным последовательным алгоритмом (каждое ребро посещается ровно один раз). Как следствие этого, производительность этого последовательного алгоритма на практике часто не уступает производительности последовательных алгоритмов, вынужденных исполнять большее число операций, чем в алгоритме Тарьяна.
  
=== Математическое описание ===
+
=== Математическое описание алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
 +
Алгоритм состоит в вызове следующей функции от произвольной непосещённой вершины графа, до тех пор, пока не останется непосещённых вершин.
 +
 
 +
<source lang="pascal">
 +
var i: integer // счётчик вершин
 +
var s: stack  // стек вершин
 +
var c: list    // список вершин в текущей компоненте
 +
i = 0
 +
s = {}
 +
c = {}
 +
function scc(v: vertex)
 +
lowlink[v] = number[v] = i = i + 1
 +
s.push(v)
 +
for w in neighbors(v) do
 +
if number[w] == nil then
 +
scc(w)
 +
lowlink[v] = min(lowlink[v], lowlink[w])
 +
else
 +
if w in s then
 +
lowlink[v] = min(lowlink[v], lowlink[w])
 +
end
 +
end
 +
end
 +
if lowlink[v] == number[v] then
 +
// v – корень компоненты
 +
w = s.pop()
 +
while w != nil and number[w] >= number[v] do
 +
c.add(w)
 +
w = s.pop()
 +
end
 +
end
 +
end
 +
</source>
 +
 
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
  
Строка 13: Строка 50:
  
 
=== Информационный граф ===
 
=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
  
 
Возможности параллелизации алгоритма Тарьяна сильно ограничены, поскольку он основан на [[Поиск в глубину (DFS)|поиске в глубину]]. Параллельный [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> основан на тех же свойствах графа и может использовать любое остовное дерево.
 
Возможности параллелизации алгоритма Тарьяна сильно ограничены, поскольку он основан на [[Поиск в глубину (DFS)|поиске в глубину]]. Параллельный [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> основан на тех же свойствах графа и может использовать любое остовное дерево.
  
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма===
+
=== Свойства алгоритма ===
== Программная реализация алгоритмов ==
+
 
 +
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
=== Результаты прогонов ===
=== Масштабируемость алгоритма и его реализации ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
+
 
 
== Литература ==
 
== Литература ==
  
 
<references />
 
<references />
 +
 +
[[Категория:Начатые статьи]]
 +
 +
[[en:Tarjan's biconnected components algorithm]]

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


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

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

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

Процесс поиска в глубину является существенно последовательным (inherently sequential) и практически не параллелизуется. Вместе с тем, алгоритм Тарьяна по-видимому является максимально возможно эффективным последовательным алгоритмом (каждое ребро посещается ровно один раз). Как следствие этого, производительность этого последовательного алгоритма на практике часто не уступает производительности последовательных алгоритмов, вынужденных исполнять большее число операций, чем в алгоритме Тарьяна.

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

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

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

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

Алгоритм состоит в вызове следующей функции от произвольной непосещённой вершины графа, до тех пор, пока не останется непосещённых вершин.

var i: integer // счётчик вершин
var s: stack   // стек вершин
var c: list    // список вершин в текущей компоненте
i = 0
s = {}
c = {}
function scc(v: vertex)
	lowlink[v] = number[v] = i = i + 1
	s.push(v)
	for w in neighbors(v) do
if number[w] == nil then
	scc(w)
	lowlink[v] = min(lowlink[v], lowlink[w])
else
	if w in s then 
		lowlink[v] = min(lowlink[v], lowlink[w])
	end
end
end
	if lowlink[v] == number[v] then
		// v – корень компоненты
		w = s.pop()
		while w != nil and number[w] >= number[v] do
			c.add(w)
			w = s.pop()
		end
	end
end

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

Последовательная сложность алгоритма Тарьяна составляет [math]O(m)[/math], так как в процессе поиска в ширину выполняется ограниченное количество операций для каждой вершины и каждого ребра.

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

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

Возможности параллелизации алгоритма Тарьяна сильно ограничены, поскольку он основан на поиске в глубину. Параллельный алгоритмом Тарьяна-Вишкина[2] основан на тех же свойствах графа и может использовать любое остовное дерево.

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.
  2. Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.