Parallel Implementation of Prim’s Algorithm

Graphs are widely used in manyapplications. Some of the applications that usedgraph theory are: analysis of electrical circuits,route planning, genetics, social sciences and soon. The system is based on sequential algorithm ofPrim and will focus on its parallelization targetingon message passing through the server and theclient. This system will introduce 2 strategies toparallel the sequential Prim’s algorithm forfinding minimum spanning tree (MST) on clientserverarchitecture. In the first strategy, the serverwill compute the global minimum spanning tree byasking the local minimum-weight edges of theclient every step of the computation. Server andclient follow every step of the Prim Algorithm andexchange the messages back and forth until theglobal minimum spanning tree is achieved. In thelater strategy, the server and client parallelcompute the local minimum spanning tree basedon their sub-graphs and then the client sends itslocal minimum spanning tree to the server. Theserver combines all local minimum spanning treesand calculates a global one