Графовое программирование в Scheme

Я новичок в Scheme, уже некоторое время использую MIT Scheme. Я пытаюсь понять, как реализовать популярные алгоритмы графов, такие как алгоритмы кратчайшего пути, BFS, DFS. Есть ли какие-нибудь учебники, которые могли бы помочь мне разобраться в рекурсии, которая будет задействована, а также в соответствующих структурах данных? Я пробовал искать в Googling, но это не дало мне хороших результатов.

EDIT: Я прошу прощения за то, что не был более конкретен ранее. Мой вопрос касался обхода всего графа, а не поиска пути между узлами start и goal. Итак, учитывая граф G(V, E), где V - множество вершин, а E - множество ребер, начиная с любой вершины n, какой путь должен быть сгенерирован, чтобы в конце этого обхода все вершины были посещены.

Большинство реализаций, которые я нашел, пока гуглил, были с узлом start и goal. В моей версии (один из ответов), выбирается одна вершина, а посещаются все остальные.

Возьмем, например, следующий граф:-

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

Эта DAG имеет (4->2), (2->3), (5->6) и (5->7), которые я не смог изобразить на диаграмме. :-)

Путь, пройденный начиная с 1, может быть таким:

(1, 2, 3, 4, 5, 6, 7)

6
задан Gooner 3 February 2012 в 07:57
поделиться