For the sake of generality, I have refactored the code of the breadth-first search (BFS) algorithm in order to accommodate both the tree and the graph-search versions. This has to do with the ability of the algorithm to deal with redundant paths, whether if they are to be taken into account (graph-search, as it is described in pseudocode in the book) or not (tree-search). The bulk of the code has been redefined as a generic abstract data type (ADT) search algorithm, which has an additional flag to use the explored set or not, see Figure 1 (changes are highlighted).

Figure 1. Abstract data type search algorithm.

## @deftypefn {Function File} {@var{solution} =} adt_search (@var{problem}, @var{start}, @var{finish}, @var{treegraph}, @var{insert})
## Abstract data type search algorithm.
##
## PRE:
## @var{problem} must be the cost-weighted adjacency matrix.
## @var{start} must be the starting node index.
## @var{finish} must be the finishing node index.
## @var{treegraph} must be the tree/graph version flag. Zero is
## tree-version.
## @var{insert} must be function handle to manage the insertion into
## the frontier.
##
## POST:
## @var{solution} is the solution path. State set to zero if failure.
## @end deftypefn

## Author: Alexandre Trilla <alex@atrilla.net>

function [solution] = adt_search(problem, start, ...
  finish, treegraph, insert)

  % inits
  node.state = start;
  node.parent = [];
  node.cost = 0;

  if (node.state == finish)
    solution = node;
  else
    frontier = [node];
    explored = [];
    found = 0;
    while (~found)
      if (numel(frontier) == 0)
        solution.state = 0;
        found = 1;
        break;
      endif
      % pop frontier
      node = frontier(1);
      frontier = frontier(2:end);
      % explore
      if (treegraph)
        explored(numel(explored)+1) = node.state;
      endif
      for i = 1:size(problem, 2)
        if (problem(node.state, i)>0)
          if (i ~= node.state)
            % by default, continue exploration
            notExpl = 1;
            if (treegraph)
              notExpl = ~sum(explored == i);
            endif
            if (notExpl)
              inFront = 0;
              for j = 1:numel(frontier)
                if (frontier(j).state == i)
                  inFront = 1;
                  break;
                endif
              endfor
              if (~inFront)
                % expand search space
                child.state = i;
                path = node.parent;
                path = [path node.state];
                child.parent = path;
                child.cost = node.cost + problem(node.state, i);
                % check goal
                if (i == finish)
                  solution = child;
                  found = 1;
                  break;
                else
                  frontier = insert(frontier,child);
                endif
              endif
            endif
          endif
        endif
      endfor
    endwhile
  endif

endfunction

Note that the ADT-search algorithm is also given a function handle to manage the insertion of a node into the frontier. The rationale for doing it is mainly to avoid the Don’t-Repeat-Yourself principle, i.e., the pragmatic programmer’s tip number 11. The benefit of this will come when we get to depth-first search. Stay tuned! Now, if this ADT-search algorithm is given a handle to a function that manages the frontier as a queue, see Figure 2, the functional behaviour of BFS remains the same.

Figure 2. Queue insertion function.

## @deftypefn {Function File} {@var{insertion} =} ins_fifo(@var{frontier}, @var{node})
## Queue insertion.
##
## PRE:
## @var{frontier} must be a struct array for the frontier.
## @var{node} must be a struct for the node.
##
## POST:
## @var{insertion} is the extended frontier.
## @end deftypefn

## Author: Alexandre Trilla <alex@atrilla.net>

function [insertion] = ins_fifo(frontier, node)

  insertion = [frontier node];

endfunction

A final note on the application scenario of BFS

The BFS algorithm (and in fact the rest of search routines you will see shortly) is to be deployed on environments that are deterministic, observable, static, and completely known. Otherwise, if the application scenario at hand does not display these characteristics, you simply can’t design an agent that performs actions to accomplish its goals with BFS.
BFS is a search strategy that seeks the shallowest path to the solution, it is complete (so it always finds a solution if there is one, at least), it is optimal for unit step costs, but it has exponential space complexity, which makes it infeasible for large-space search problems. Also note that the description of the search problem must be discrete, therefore the trees, graphs and their adjacency matrices. If continuous environments are to be searched with these methods, they must be discretised first, thus yielding a quantisation error according to the granularity of the grid of use. Or else use some common sense to reasonably represent the problem in discrete and tractable terms, like the BFS example with the map of Germany.