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) $