Thuật toán cây bao trùm tối thiểu song song

Question

Tôi biết một số thuật toán cây bao trùm tối thiểu: Boruvka, Prim và Kruskal. Mà trong số họ có thể được thực hiện trong thời trang song song?

Cảm ơn!

Answer 1

Trong số 3 thuật toán này, chỉ có thuật toán Boruvka mới có thể dễ dàng song song.

Báo giá từ the description of Boruvka algorithm on algoritmy.net:

Một lợi thế đáng kể của thuật toán của Borůvka là được có thể dễ dàng song song, bởi vì sự lựa chọn của rìa đi giá rẻ nhất cho mỗi thành phần là hoàn toàn không phụ thuộc vào sự lựa chọn được thực hiện bởi các thành phần khác .