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

Различные стратегии выбора F' на шагу 2(а) могут привести к получению различных <math>B_i \;</math>. Тем не менее, B[1, i] всегда является подмножеством <math>T^*_G \;</math> и порождает <math>2^i \;</math>-лес. В частности, <math>B[1, \lfloor log \; n \rfloor ]</math> порождает ровно одно дерево, которым и является <math>T^*_G \;</math>. Используя стандартные техники распараллеливания алгоритмов, каждый шаг можно реализовать за время O(log n) на машине EREW PRAM с линейным числом процессоров (см, например, [5]). Таким образом, минимальное остовное дерево <math>T^*_G \;</math> может быть найдено за время <math>O(log^2 \; n)</math>. Большинство параллельных алгоритмов поиска MST используют подобный подход. Параллельные алгоритмы являются «последовательными» в том смысле, что вычисление <math>B_i \;</math> начинается только после нахождения <math>B_{i-1} \;</math>.