Алгоритм Шилоаха-Вишкина поиска компонент связности: различия между версиями
| [досмотренная версия] | [досмотренная версия] |
Apaokin (обсуждение | вклад) Нет описания правки |
ASA (обсуждение | вклад) Нет описания правки |
||
| Строка 34: | Строка 34: | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== Возможные способы и особенности параллельной реализации алгоритма === | === Возможные способы и особенности параллельной реализации алгоритма === | ||
=== | === Результаты прогонов === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Текущая версия от 11:49, 6 июля 2022
| Алгоритм Шилоаха-Вишкина | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O((m + n) \ln n) }[/math] |
| Объём входных данных | [math]\displaystyle{ O(m) }[/math] |
| Объём выходных данных | [math]\displaystyle{ n }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ O(\ln n) }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ n + 2m }[/math] |
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Шилоаха-Вишкина[1] (англ. Shiloach-Vishking Algorithm) предназначен для поиска компонент связности неориентированного графа. Используется структура данных, аналогичная системе непресекающихся множеств. В модели CRCW PRAM алгоритм приписывает каждой вершине идентификатор компоненты связности за время [math]\displaystyle{ O(\ln n) }[/math] на [math]\displaystyle{ n + 2m }[/math] процессорах.
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Алгоритм изначально параллельный и при последовательной реализации фактически превращается в систему непресекающихся множеств.
Последовательная сложность алгоритма
Последовательная сложность алгоритма Шилоаха-Вишкина [math]\displaystyle{ O((m + n) \ln n) }[/math].
Информационный граф
Ресурс параллелизма алгоритма
Время работы алгоритма составляет [math]\displaystyle{ O(\ln n) }[/math] на [math]\displaystyle{ n + 2m }[/math] процессорах в модели CRCW PRAM.
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Возможные способы и особенности параллельной реализации алгоритма
Результаты прогонов
Выводы для классов архитектур
Литература
- ↑ Shiloach, Yossi, and Uzi Vishkin. “An [math]\displaystyle{ O(\log n) }[/math] Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.