我有一个 BFS 的实现,我从其他地方得到并稍作修改,但我的输入有问题。
它需要一个图形,并将其作为 '((a b c) (b c) (c d))
但是我给它的输入是一个加权图……我知道它对 BFS 没有用,但我稍后会使用权重。这个输入看起来像
'(<br/>
(a (b 3) (c 1))<br/>
(b (a 3) (d 1))<br/>
(c (a 1) (d2) (e 2))<br/>
)
等等。
我的代码:
(defun shortest-path (start end net)
(BFS end (list (list start)) net))
(defun BFS (end queue net)
(if (null queue)
nil
(expand-queue end (car queue) (cdr queue) net)))
(defun expand-queue (end path queue net)
(let ((node (car path)))
(if (eql node end)
(reverse path)
(BFS end
(append queue
(new-paths path node net))
net))))
(defun new-paths (path node net)
(mapcar #'(lambda (n)
(cons n path))
(cdr (assoc node net))))
我只是不确定我最有可能在哪里修改它以接受新的样式列表,或者制作一个帮助函数来正确格式化它?
最佳答案
您需要指定代表图表的列表的含义。目前你只给出了一个示例列表。
当图的语法如下:
graph = (node*)
node = (name nextnodename*)
name = SYMBOL
nextnodename = SYMBOL
那么转换函数可能是:
(defun convert-graph (graph)
(mapcar (lambda (node)
(destructuring-bind (name . nodes) node
(cons name (mapcar #'first nodes))))
graph))
或者如果您可能需要其他提取功能:
(defun convert-graph (graph &key (key #'first))
(mapcar (lambda (node)
(destructuring-bind (name . nodes) node
(cons name (mapcar key nodes))))
graph))
例子:
(convert-graph '((a (b 3) (c 1))
(b (a 3) (d 1))
(c (a 1) (d 2) (e 2)))
:key #'first)
((A B C) (B A D) (C A D E))
现在您可能需要删除重复的链接。但这取决于您的图形描述的语法和语义。
关于graph - LISP - 广度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5614568/