Course project of Advances in Parallel Computing In real-world, every sector like Social media, networks etc are represented by using large-scale graphs. Analyzing this graph is a common problem and in most cases, traditional breadth-first search (BFS) is used. But for analyzing large-scale graphs the sequential BFS algorithms is not enough, it needs more computation power and storage. Traversing the large-scale graph can be done by using the parallel “Breadth-First” search (BFS) algorithm. In this study, I represented a parallel “Breadth-First” search (BFS) algorithm which will be efficient for large graphs.The parallel algorithm is implemented by using the 2D partitioning technique in order to get perfect load balance in every processor. The algorithm can solve any large dense and undirected graph in a small amount of time like the sequential algorithm.