Internal Design of Breadth-first Search¶
Bread-first Search is an algorithm that traverse graph data structures. It starts from a source vertex and explores its neighbor vertices at the present depth level before moving on to the next depth level.
The implemented Breadth-first Search is based on a First-In-First-Out execution queue. Below is the pseudo-code of the algorithm:
procedure BFS(graph, source) for each vertex v in graph discover(v) := positive infinity discover(source) := 0 dtime := 0 cnt_bfr := 1 cnt_cur := 0 cnt_nxt := 0 cnt_lvl := 0 push source into Q while Q is not empty u := pop Q cnt_cur++ for each edge(u,v) in graph if discover(v) == positive infinity then discover(v) := dtime level(v) := cnt_lvl parent(v) := u push v into Q dtime++ cnt_nxt++ end if end for finish(u) := dtime dtime++ if cnt_cur == cur_bfr then cnt_bfr := cnt_nxt cnt_cur := 0 cnt_nxt := 0 cnt_lvl ++ end if end while return (level, parent, discover, finish)
Here, graph is a graph with a list of vertices and a list of edges. source is the start vertex of the algorithm. Q is a first-in-first-out queue.
The input should be a directed graph in compressed sparse row (CSR) format. The result include level, parent, discover and finish. Level is a list which shows the final distance level to the source vertex. Parent is a list which shows the parent vertex of every vertex in the BFS. Discovery shows when a vertex is discovered in the BFS. Finish shows when all one-hop children vertices of a vertex are processed.
The algorithm implemention is shown in the figure below:
There are 4 functional blocks as shown in the figure:
- GetVertex is responsible to load the next vertex in the queue and pass it to the ReadGraph.
- ReadGraph collects all next hop vertices and pass them to the next module.
- ReadColor check each next hop vertex whether it has already been discovered in ealier stages of the BFS. This module only passes first discovered vertices to the next block.
- When the 3rd functional block ends, WriteRes update the discovery, finish, level and parent value accordingly. And also this block push all the vertices collected from block 3 into Queue.
This system starts from pushing the source vertex into the queue and iterate until the queue is empty.