Scheme中的图编程

Question

我是 Scheme 的新手，使用 MIT 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

广度优先和深度优先搜索都作为示例出现在 How To Design Programs 中, 从第 28 节开始.我认为这可能最具体地帮助您解决有关在图形处理中使用递归的问题。