스레드를 사용하여 Kruskal의 알고리즘 구현

Question

Kruskal의 알고리즘을 구현하고 있으며 스레드를 사용하고 싶습니다. 그러나 나는 이것을 할 알고리즘에 대해 충분히 알고 있는지 확실하지 않습니다.

내가 상상하는 것은 그래프의 다른 부분이 마지막에 해결되고 연결될 것이라는 것입니다. 누구든지 나를 올바른 방향으로 가리킬 수 있습니까? 감사.

Answer 1

에서 위키 백과

연구는 최소 스패닝 트리 문제를 고도로 평행 한 방식으로 해결하는 데 중점을 두었습니다. 선형 수의 프로세서를 사용하면 O (LOGN) 시간의 문제를 해결할 수 있습니다. David A. Bader와 Guojing Cong의 희소 그래프의 최소 스패닝 숲을 계산하기위한 빠른 공유 메모리 알고리즘 "은 최적화 된 순차적 알고리즘보다 8 개 프로세서에서 MST를 5 배 빠르게 계산할 수있는 실용적인 알고리즘을 보여줍니다. [9] 일반적으로 병렬 알고리즘은 Boruvka의 알고리즘을 기반으로하며, 특히 Kruskal의 알고리즘은 추가 프로세서로 확장되지 않습니다.

따라서 해당 논문에서 언급 된 알고리즘을 살펴볼 수 있지만 Kruskal은 아마도 여러 스레드의 이점을 얻지 못할 것입니다.

Answer 2

MST에 대한 Kruskal의 알고리즘은 가장 잘 지정된 순서로 가장자리를 고려하기 때문에 병렬화하기가 어렵습니다. 당신은 살펴 봐야합니다 Boruvka 's 부분 MST의 각 하위 트리에서 독립적으로 작동 할 수 있으므로 병렬화하기 쉬운 알고리즘.