Это действительно поиск в ширину

Question

Ниже приведен фрагмент псевдокода поиска в ширину на стр.303 OnLisp. Для приведенного ниже графика он сначала обработает узел 1, а затем поместит узлы 2, 3 и 4 в очередь, а затем просто итеративно вызовет себя снова. Затем он продолжит работу с узлом 4, который находится в начале очереди. Это в свою очередь поместит узлы 7 и 8 в начало очереди и так далее.

Наконец, пройденный путь будет 1->4->7-11->12->8->3->2->5->9->10->6, что является первым поиском по глубине. Я здесь не прав?

(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

При поиске по ширине используются очереди "первый пришел - первый вышел" для элементов, которые он будет проходить.

Стоит посмотреть на первый узел (1)потом хватай своих детей (2, 3, 4) и заполните список в этом порядке. Теперь посмотрите на первый элемент в списке и возьмите его дочерние элементы. (5, 6) и добавьте их в конец списка вещей, чтобы посмотреть (3, 4, 5, 6),

Продолжайте повторять это только для первого элемента.

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

Делая сначала вход, последний выход (зацикливаясь на самом последнем добавленном элементе, как вы делаете), вы создаете поиск в глубину.