Я новичок в 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)