Programación de gráficos en el Esquema

Question

Soy nuevo en Scheme, he estado usando MIT Scheme por algún tiempo. Estoy tratando de entender cómo implementar algoritmos de gráficos populares como los algoritmos de ruta más cortos, BFS, DFS. ¿Hay algún tutorial que pueda ayudarme a comprender la recursividad que estaría involucrada, junto con las estructuras de datos apropiadas? He intentado buscar en Google, pero eso no terminó dándome buenos resultados.

EDIT: Pido disculpas por no ser más específico anteriormente. Mi pregunta era acerca de atravesar el gráfico completo, y no encontrar la ruta entre start y meta node. Así, dada una gráfica G (V, E), en donde V es el conjunto de vértices y E es el conjunto de borde, a partir de cualquier nodo n, ¿cuál es la ruta de acceso generado de modo que al final de esta travesía, todos los nodos son visitados.

mayoría de las implementaciones que he encontrado buscando en Google, mientras que eran los que tenían el comienzo y objetivo nodo. Mi versión (una de las respuestas), elige un vértice y visita todos los demás.

Tomemos, por ejemplo, el siguiente gráfico: -

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

Este DAG tiene (4-> 2), (2-> 3), (5-> 6) y (5-> 7), que no puedo representar en el diagrama. :-)

El camino recorrido a partir de podrían ser:

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

Answer 1

Tomó algo de tiempo, ¡pero finalmente funcionó! Mi salida es la secuencia en la que los nodos se habrían visitado en el cruce a través de DFS.

Tenga en cuenta que todavía estoy aprendiendo Scheme, y mi enfoque de programación podría no ser el mejor.Si encuentra algo incorrecto, incorrecto o algo que pueda expresarse mejor, ¡deje un comentario!

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

entrada de la muestra puede ser: (DFS '((1 (2)) (2 (3)) (3) (4) (4 (2)) (5 ​​(3 6)) (6 ())))

Answer 2

primero en amplitud y profundidad-primero buscar tanto aparecen como ejemplos en How To Design Programs, comenzando en la sección 28. Creo que esto probablemente lo ayudará más específicamente con su pregunta sobre los usos de la recursividad en el procesamiento de gráficos.

Answer 3

Si usted representa gráficos de este tipo, es decir, como una lista de nombres de nodos y los nombres de sus vecinos:

(define Graph 
    '((A (B E)) 
    (B (E F)) 
    (C (D))) 

que tiene la ventaja de que incluso se puede representar gráficos cíclicos sin recurrir a la modificación destructiva de su estructura de datos (set-cdr! etc.), siempre que permita múltiples entradas en la lista para cada clave.

Alternativamente, podría almacenar no sólo los nombres, pero la representación completa de cada vecino en una lista, por lo que se puede caminar el gráfico sin hacer ningún búsquedas de nombre:

(define node-name car) 
(define node-children cdr) 
(define node-first-child cadr) 

(node-first-child (node-first-child node1)) 

para hacer una gráfica cíclica este sin embargo, necesitaría usar set! o alguna variante. Entonces la mejor representación realmente depende de la aplicación.