0

他の場所で入手して少し変更した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))))

新しいスタイルリストを受け入れるためにどこを変更する必要があるのか​​、またはヘルプ関数を作成して正しくフォーマットする必要があるのか​​がわかりません。

4

1 に答える 1

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

ここで、重複するリンクを削除する必要があるかもしれません。ただし、これはグラフ記述の構文とセマンティクスによって異なります。

于 2011-04-11T09:57:50.860 に答える