Parallel Implementation of Prim’s Algorithm

Abstract

Graphs are widely used in many applications. Some of the applications that used graph theory are: analysis of electrical circuits, route planning, genetics, social sciences and so on. The system is based on sequential algorithm of Prim and will focus on its parallelization targeting on message passing through the server and the client. This system will introduce 2 strategies to parallel the sequential Prim’s algorithm for finding minimum spanning tree (MST) on clientserver architecture. In the first strategy, the server will compute the global minimum spanning tree by asking the local minimum-weight edges of the client every step of the computation. Server and client follow every step of the Prim Algorithm and exchange the messages back and forth until the global minimum spanning tree is achieved. In the later strategy, the server and client parallel compute the local minimum spanning tree based on their sub-graphs and then the client sends its local minimum spanning tree to the server. The server combines all local minimum spanning trees and calculates a global one.