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.