Is this really a breadth first search

Question

There is a piece of pseudo code of a breadth first search on P.303 of OnLisp which is show below. For the graph below, it will first process node 1, and then put node 2, 3 and 4 into the queue and then just iteratively call itself again. Then, it will proceed with node 4, which is at the beginning of the queue. This in turn will put node 7 and 8 into beginning of the queue and so on.

Finally, the path it traversed will be 1->4->7-11->12->8->3->2->5->9->10->6 which is depth first search. Am I wrong here?

(define (path node1 node2)
  (bf-path node2 (list (list node1))))

(define (bf-path dest queue)
  (if (null? queue)
      '@
      (let* ((path (car queue))
             (node (car path)))
        (if (eq? node dest)
            (cdr (reverse path))
            (bf-path dest
                    (append (cdr queue)
                    (map (lambda (n)
                           (cons n path))
                         (neighbors node))))))))

Answer 1

A breadth first search utilizes the first in, first out queue for elements it will traverse.

It should look at the first node (1), then grab its children (2, 3, 4) and populate a list in that order. Now look at the first element in the list and grab its children (5, 6) and add them to the end of the list of things to look at (3, 4, 5, 6).

Keep repeating this on the first element only.

3 -> (4, 5, 6)
4 -> (5, 6, 7, 8)
5 -> (6, 7, 8, 9, 10)
6 -> (7, 8 , 9, 10)
7 -> (8, 9, 10, 11, 12)
8 -> (9, 10, 11, 12)
9 -> (10, 11, 12)
10 -> (11, 12)
11 -> (12)
12 -> ()

By doing first in, last out (looping on the most recently added element as you are doing), you create a depth first search.