Parallel Implementation of Breadth-First Search (BFS) Algorithm

Optimizing BFS Algorithm on Undirected Graph represented in Adjacency Matrix using Core-Affine Threads

It is a powerful technique of systematically traversing the edges of a given graph, simultaneously, such every edge is traversed once and also each vertex is visited atleast once.

Breadth-First Traversal

BFS employs the following rules:

1. Visit the adjacent unvisited vertex. Mark it as visited. Insert it in a queue.
2. If no adjacent vertex is found, remove the first vertex from the queue.
3. Repeat Rule 1 and Rule 2 until queue is empty.

Serial Algorithm

1. One queue for the graph.
2. Apply BFS algorithm.

Parallel Algorithm

1. One global main queue for the graph.
2. One local queue each processor.
3. Apply BFS algorithm.

Compiling and Executing

javac *.java java Main

• (e.g.) java Main 5000 4
• (e.g.) java Main 5000 8

Results

1. Parallel BFS with a graph of 5000 nodes and 4 processors: ~ 5.687 seconds
2. Serial BFS with a graph of 5000 nodes and 4 processors: ~ 8.046 seconds
3. Parallel BFS with a graph of 5000 nodes and 8 processors: ~ 4.672 seconds
4. Serial BFS with a graph of 5000 nodes and 8 processors: ~ 8.327 seconds

Applications

1. Finding the shortest path between two nodes u and v, with path length measured by number of edges (an advantage over depth-first search).
2. Finding the solution of a lights-out game problem.
3. Many more!