LISP - 廣度優先搜索

Question

我有一個BFS的實現我得到了其他地方，並稍加修改，但我有其輸入問題。
它需要一個圖表，並將其視爲'（（abc）（bc）（cd）） 但我給它的輸入是一個加權圖...我知道這對BFS沒有用，但是我稍後使用更靠後的權重。此輸入看起來像
'(
(a (b 3) (c 1))
(b (a 3) (d 1))
(c (a 1) (d2) (e 2))
)
依此類推。

我的代碼：

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

我只是不知道在哪裏，我需要最有可能修改它以接受新的樣式列表，或者做一個幫助功能，以正確的格式呢？

Answer 1

您需要指定表示圖表的列表。目前您只列出了一個示例列表。

當圖表語法有像：

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

現在您可能需要刪除重複的鏈接。但這取決於圖形描述的語法和語義。