Алгоритм Шилоаха-Вишкина поиска компонент связности
| Алгоритм Шилоаха-Вишкина | |
| Последовательный алгоритм | |
| Последовательная сложность | [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.