Scheme中的图形编程

Question

我是Scheme的新手,现在已经使用麻省理工学院计划.我试图了解如何实现流行的图算法,如最短路径算法,BFS,DFS.是否有任何教程可以帮助我理解所涉及的递归以及相应的数据结构？我试过谷歌搜索,但这并没有给我带来好结果.

编辑:我为之前没有更具体的事情道歉.我的问题涉及遍历整个图,而没有找到开始和目标节点之间的路径.因此,给定图G(V,E),其中V是顶点集,E是边集,从任何节点n开始,生成的路径是什么,以便在遍历结束时访问所有节点.

我在谷歌搜索时发现的大多数实现都是具有开始和目标节点的实现.我的版本(答案之一),选择一个顶点,并访问所有其他顶点.

举例来说,如下图: -

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

该DAG具有(4-> 2),(2-> 3),(5-> 6)和(5-> 7),我无法在图中表示.:-)

从1开始遍历的路径可能是:

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