쓰레드를 이용한 kruskal의 알고리즘 구현

Question

저는 Kruskal의 알고리즘을 구현 중이며 쓰레드를 활용하고 싶습니다. 그러나 나는 이것을 수행하는 알고리즘에 대해 충분히 잘 모르겠다.

내가 상상 한 것은 그래프의 다른 부분이 해결되어 결국 연결된다는 것입니다. 누구든지 올바른 방향으로 나를 가리킬 수 있습니까? 감사.

Answer 1

Wikipedia

에서 연구는 높은 병렬 방식으로 최소 스패닝 트리 문제 해결에 초점을 맞추고있다. 선형 숫자의 프로세서를 사용하면 O (로그인) 시간에 문제를 해결할 수있는 입니다. 2003 년 논문은 "빠른 가 공유 메모리 알고리즘 스파 스 그래프의 최소 스패닝 숲을 컴퓨팅을위한"데이비드 A. 베이더와 Guojing 콩으로는 보다 8 개 프로세서에 5 배 빠른 MSTS를 계산할 수있는 실용적인 알고리즘을 보여줍니다 최적화 순차 알고리즘 [9] 일반적으로 병렬 알고리즘은 Boruvka의 알고리즘 -Plim의 을 기반으로 한 이며 특히 Kruskal의 알고리즘 은 추가 프로세서에 해당하지 않습니다.

따라서이 기사에서 언급 한 알고리즘을 살펴 보았을 지 모르지만 Kruskal은 아마 여러 스레드로부터 이익을 얻지 못할 것입니다.

Answer 2

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