Программирование графа на схеме - PullRequest
Новая
       51

Программирование графа на схеме

6 голосов
/ 27 января 2012

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

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

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

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

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

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

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

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

Ответы [ 3 ]

4 голосов
/ 27 января 2012

Поиск в ширину и в глубину происходит как примеры в Как проектировать программы , начиная с раздела 28 .Я думаю, что это, вероятно, поможет вам наиболее конкретно ответить на вопрос об использовании рекурсии в обработке графов.

1 голос
/ 02 февраля 2012

Потребовалось время, но я наконец-то заработал! Мой вывод - последовательность, в которой узлы были бы посещены при обходе через 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 ())))

1 голос
/ 30 января 2012

Если вы представляете такие графы, то есть как список имен узлов и имен их соседей: 

(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! или какой-либо другой вариант.Так что лучшее представление действительно зависит от приложения.

...