3.15 示例：最短路径 (Example: Shortest Path)

图 3.12 包含一个搜索网络中最短路径的程序。函数 shortest-path 接受一个起始节点，目的节点以及一个网络，并返回最短路径，如果有的话。

在这个范例中，节点用符号表示，而网络用含以下元素形式的关联列表来表示：

(node . neighbors)

所以由图 3.13 展示的最小网络 (minimal network)可以这样来表示：

(setf min '((a b c) (b c) (c d)))

(defun shortest-path (start end net)
  (bfs end (list (list start)) net))
(defun bfs (end queue net)
  (if (null queue)
      nil
      (let ((path (car queue)))
        (let ((node (car path)))
          (if (eql node end)
              (reverse path)
              (bfs end
                   (append (cdr queue)
                           (new-paths path node net))
                   net))))))
(defun new-paths (path node net)
  (mapcar #'(lambda (n)
              (cons n path))
          (cdr (assoc node net))))

图 3.12 广度优先搜索(breadth-first search)

图 3.13 最小网络

要找到从节点 a 可以到达的节点，我们可以：

> (cdr (assoc 'a min))
(B C)

图 3.12 程序使用广度优先的方式搜索网络。要使用广度优先搜索，你需要维护一个含有未探索节点的队列。每一次你到达一个节点，检查这个节点是否是你要的。如果不是，你把这个节点的子节点加入队列的尾端，并从队列起始选一个节点，从这继续搜索。借由总是把较深的节点放在队列尾端，我们确保网络一次被搜索一层。

图 3.12 中的代码较不复杂地表示这个概念。我们不仅想要找到节点，还想保有我们怎么到那的纪录。所以与其维护一个具有节点的队列 (queue)，我们维护一个已知路径的队列，每个已知路径都是一列节点。当我们从队列取出一个元素继续搜索时，它是一个含有队列前端节点的列表，而不只是一个节点而已。

函数 bfs 负责搜索。起初队列只有一个元素，一个表示从起点开始的路径。所以 shortest-path 调用 bfs ，并传入 (list (list start)) 作为初始队列。

bfs 函数第一件要考虑的事是，是否还有节点需要探索。如果队列为空， bfs 返回 nil 指出没有找到路径。如果还有节点需要搜索， bfs 检查队列前端的节点。如果节点的 car 部分是我们要找的节点，我们返回这个找到的路径，并且为了可读性的原因我们反转它。如果我们没有找到我们要找的节点，它有可能在现在节点之后，所以我们把它的子节点（或是每一个子路径）加入队列尾端。然后我们递回地调用 bfs 来继续搜寻剩下的队列。

因为 bfs 广度优先地搜索，第一个找到的路径会是最短的，或是最短之一：

> (shortest-path 'a 'd min)
(A C D)

这是队列在我们连续调用 bfs 看起来的样子：

((A))
((B A) (C A))
((C A) (C B A))
((C B A) (D C A))
((D C A) (D C B A))

在队列中的第二个元素变成下一个队列的第一个元素。队列的第一个元素变成下一个队列尾端元素的 cdr 部分。

在图 3.12 的代码不是搜索一个网络最快的方法，但它给出了列表具有多功能的概念。在这个简单的程序中，我们用三种不同的方式使用了列表：我们使用一个符号的列表来表示路径，一个路径的列表来表示在广度优先搜索中的队列 [4] ，以及一个关联列表来表示网络本身。