Lisp--Shortest Path(bfs和dfs)

用Lisp实现寻找有向图中最短路径（深度优先算法和广度优先算法）

先来看一下图的存储格式:

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

min:

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

min2:

;;;将所有node中未加入的节点加入path中
(defun new-paths (path node net)
	(mapcar #'(lambda (n)
						(cons n path));;;注意此函数会依次作用于下面的参数上(mapcar的效果)
					(cdr (assoc node net))));;;取出与node关联的所有节点
;;;bfs广度优先算法
(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))))))
//dfs深度优先算法
(defun dfs (end queue net)
	(if (null queue)
		nil
		(let ((path (car queue)))
		 (let ((node (car path)))
		  (if (eql node end)
		  	(reverse path)
		   	 	(dfs end
		   	 		(append 
		   	 			(new-paths path node net)
		   	 			(cdr queue));;;这里的顺序是与上面bfs算法差别之一
		   	 		net))))))
//
(defun shortest-path-bfs (start end net)
	(bfs end (list (list start)) net))
//
(defun shortest-path-dfs (start end net)
	(dfs end (list (list start)) net))

以下是在lispbox-0.7中运行的结果:

在图min中运用bfs算法时，每次调用bfs时queue的值如下：
((a))
((b a) (c a))
((c a) (c b a))
((c b a) (d c a))
((d c a) (d c b a))

在图min中运用dfs算法时，每次调用dfs时queue的值如下：
((a))
((b a) (c a))
((c b a) (c a))
((d c b a) (c a))

在图min2中运用bfs算法时，每次调用bfs时queue的值如下：
((a))
((b a) (c a))
((c a) (c b a) (d b a))
((c b a) (d b a) (d c a))
((d b a) (d c a) (d c b a))

在图min2中运用dfs算法时，每次调用dfs时queue的值如下：
((a))
((b a) (c a))
((c b a) (d b a) (c a))
((d c b a) (d b a) (c a))

也许这组测试数据更有特点:

bfs算法在《ANSI_Common_Lisp》中已经给出，而dfs算法是我站在巨人的肩膀上的拙作（其实还是大师做了大部分工作），希望可以起到抛砖引玉的作用

参考:
《ANSI_Common_Lisp》—Paul Graham
《Introductory Combinatorics》 —Richard A. Brualdi