FUNCTION BFS(graph, frontier_nodes, bfs_tree, end_node) =
% terminate when either there are no more nodes in the frontier or you
find the end node %
if (#frontier_nodes == 0) or
any({node==end_node: node in frontier_nodes})
then bfs_tree
else
let
% get all the neighbors of the current frontier %
neighbors = graph->frontier_nodes;
% tag the neighbors with the node they came from and flatten %
next = flatten({{(ne,n): ne}
: n in frontier_nodes; ne in neighbors});
% remove the neighbors that have already been searched %
next = {ne in next
; p in bfs_tree->{ne:(ne,n) in next}
| p == -1};
% write into the bfs_tree the back pointers %
bfs_tree = bfs_tree<-next;
% remove duplicates by checking if you were written %
next = {ne: (ne,n) in next
; p in bfs_tree->{ne:(ne,n) in next}
| n == p}
% recurse %
in BFS(graph, next, bfs_tree, end_node) $
% The following returns the path of a tree from a node to its root %
FUNCTION TREE_PATH(node, bfs_tree) =
let next = bfs_tree[node];
in
if (next == node) then [node]
else [node] ++ TREE_PATH(next,bfs_tree) $