Алгоритм Тарьяна поиска компонент двусвязности
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
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] основан на тех же свойствах графа и может использовать любое остовное дерево.