tree - 这真的是广度优先搜索吗

Question

OnLisp 的 P.303 上有一段广度优先搜索的伪代码，如下所示。对于下图，它将首先处理节点 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 -> ()

通过执行先进后出（在您正在执行的过程中循环最近添加的元素），您可以创建深度优先搜索。