реализация алгоритма Крускала с использованием потоков

Question

Я реализую алгоритм Крускала и хотел бы использовать потоки. Однако я не уверен, что знаю достаточно об алгоритме, чтобы сделать это.

То, что я представляю, состоит в том, что в конце я бы разобрался с разными частями графика и соединился. Может кто-то указать мне верное направление? Спасибо.

Answer 1

С Википедия

Исследования были направлены на решение минимальная проблема связующего дерева в высоко распараллеленная манера. С линейное число процессоров это можно решить проблему в O (logn) время. Бумага 2003 года "Быстро Алгоритмы с общей памятью для вычислений Минимальный Охватывающий Лес Разреженный Графики »Дэвида А. Бадера и Гоцзин Конг демонстрирует прагматичный алгоритм, который может вычислить MST 5 в 8 раз быстрее, чем на оптимизированный последовательный алгоритм. [9] Как правило, параллельные алгоритмы на основе алгоритма Борувки - Прима и особенно алгоритм Крускала сделать не масштабируется, а к дополнительному процессоры.

Итак, вы можете посмотреть на алгоритм, упомянутый в этой статье, но Kruskal, вероятно, не выиграет от нескольких потоков.

Answer 2

Алгоритм Крускала для MST трудно распараллелить, потому что он рассматривает ребра в строго определенном порядке. Вам следует взглянуть на алгоритм Борувки , который легче распараллелить, поскольку он может работать на каждом поддереве частичного MST независимо.