Listing 2:

breadthfirstsearch

 
1define sub bfs 
2  by reference G = (V, E) : graph 
3  by value x : vertex 
4  local Visited : set of vertices 
5  local Boundary : set of vertices 
6  Visited = {} 
7  Boundary = { x } 
8  NextBoundary = { } 
9  while (not(Boundary = {})) do 
10    while (not (Boundary = {}) do 
11      select y from Boundary 
12      Boundary <− Boundary − y 
13      Visited <− Visited + y 
14      if not(y in Visited) then 
15        for each (y, z) in E do 
16          NewBoundary <− NewBoundary + z 
17        end for 
18      end if 
19    end while 
20    Boundary <− NextBoundary 
21    NextBoundary <− {} 
22  end while 
23end define sub