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

Question

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

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

Answer 1

От Википедия

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

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

Answer 2

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