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

通过先进后出(循环处理最近添加的元素)，您可以创建深度优先搜索。