Design and Implementation of GPU-Based Prim's Algorithm
Wei Wang, Yongzhong Huang, Shaozhong Guo · International Journal of Modern Education and Computer Science · 2011
Minimum spanning tree is a classical problem in graph theory that plays a key role in a broad domain of applications.This paper proposes a minimum spanning tree algorithm using Prim's approach on Nvidia GPU under CUDA architecture.By using new developed GPU-based Min-Reduction data parallel primitive in the key step of the algorithm, higher efficiency is achieved.Experimental results show that we obtain about 2 times speedup on Nvidia GTX260 GPU over the CPU implementation and 3 times speedup over non-primitives GPU implementation.