Schemeのグラフプログラミング

Question

私はSchemeを使い慣れていて、いまのところMIT Schemeを使用しています。私は、最短パスアルゴリズム、BFS、DFSのような一般的なグラフアルゴリズムの実装方法を理解しようとしています。適切なデータ構造とともに、関係する再帰を理解するのに役立つチュートリアルがありますか？私は周りにグーグルを試みたが、それは私に良い結果を与えることに終わらなかった。

EDIT：より具体的なものではないことをお詫び申し上げます。私の質問は、グラフ全体を走査し、開始とゴールノードの間のパスを見つけることには関係しませんでした。だから、Vは、頂点集合であり、E任意のノードNから出発して、エッジの集合であるグラフG（V、E）、与えられ、そのように生成されたパスは、の終わりに何このトラバーサル、すべてのノードが訪問されます。

グーグルで見つかったほとんどの実装は、開始点を持つものでした。とゴールノードです。私のバージョン（回答の1つ）は、1つの頂点を選択し、他のすべての頂点を訪問します。例えば

取り、次のグラフ： -

1 ----> 2   5 
     /|   /| 
    /|  /| 
    /|  /| 
    / |  / | 
/ | / | 
    4<----3 <---6  7 

このDAGは、（5-（4-> 2）、（2-> 3）、（> 6 5-）とを有しています> 7）、私は図で表現することができません。 Pathはから出発してあってもよい横断:-)

：

（1、2、3、4、5、6、7）

Answer 1

しばらく時間がかかりましたが、私は最終的にそれを得ました！私の出力は、ノードがDFSを介したトラバーサルで訪問されたシーケンスです。

私はまだSchemeしか学習していないことに注意してください。私のプログラミングアプローチは最良ではないかもしれません。あなたが間違った、間違った、またはより良い表現が可能なものを見つけた場合は、コメントを残してください！

(define (dfs graph) 
     (define (dfshelper g unvisited stack path) 
      (cond 
      ((null? unvisited) path) 
       ((null? stack) 
        (dfshelper g 
           unvisited 
           (append (list (caar unvisited)) stack) 
           path)) 
       ((memq (car stack) path) (dfshelper g 
                unvisited 
                (cdr stack) 
                path)) 
       (else (dfshelper g 
           (cdr unvisited) 
           (append (car (neighbours (car stack) g)) (cdr stack)) 
           (append path (list (car stack))))))) 

    (define (neighbours node g) 
     (cond 
     ((null? g) '()) 
     ((equal? node (caar g)) (cdar g)) 
     (else (neighbours node 
          (cdr g))))) 

    (dfshelper graph graph '() '())) 

サンプル入力があってもよい：（DFS「（（1（2））（2（3））（3（4））（4（2））（5（3 6））（6（ ））））））））））））012）

Answer 2

幅優先及び深さ優先探索両方セクション28で始まるHow To Design Programsに例として示されています。グラフ処理での再帰の使用についての質問には、おそらく最も役立つと思います。あなたはすなわちノードとその隣人の名前の名前のリストとして、このようなグラフを表す場合

Answer 3

：

(define Graph 
    '((A (B E)) 
    (B (E F)) 
    (C (D))) 

あなたもの破壊的な変更に頼ることなく巡回グラフを表現することができるという利点を持っていますあなたのデータ構造（set-cdr!等）、あなたが各キーのためのリストの複数のエントリを許可するならば。あなたが任意の名前の検索を行うことなく、グラフを歩くことができるように

代わりに、あなたは、名前が、リスト内の各ネイバーの完全な表現ではないだけを保存することができます：

(define node-name car) 
(define node-children cdr) 
(define node-first-child cadr) 

(node-first-child (node-first-child node1)) 

この巡回グラフを作成するにはただし、set!または別の方法を使用する必要があります。だから最善の表現は本当にアプリケーションに依存します。