Алгоритм Шилоаха-Вишкина поиска компонент связности
Версия от 14:49, 6 июля 2022; ASA (обсуждение | вклад)
| Алгоритм Шилоаха-Вишкина | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O((m + n) \ln n)[/math] |
| Объём входных данных | [math]O(m)[/math] |
| Объём выходных данных | [math]n[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O(\ln n)[/math] |
| Ширина ярусно-параллельной формы | [math]n + 2m[/math] |
Содержание
- 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] (англ. Shiloach-Vishking Algorithm) предназначен для поиска компонент связности неориентированного графа. Используется структура данных, аналогичная системе непресекающихся множеств. В модели CRCW PRAM алгоритм приписывает каждой вершине идентификатор компоненты связности за время [math]O(\ln n)[/math] на [math]n + 2m[/math] процессорах.
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
Алгоритм изначально параллельный и при последовательной реализации фактически превращается в систему непресекающихся множеств.
1.6 Последовательная сложность алгоритма
Последовательная сложность алгоритма Шилоаха-Вишкина [math]O((m + n) \ln n)[/math].
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Время работы алгоритма составляет [math]O(\ln n)[/math] на [math]n + 2m[/math] процессорах в модели CRCW PRAM.
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ Shiloach, Yossi, and Uzi Vishkin. “An [math]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.
