Programmazione grafica nello schema

Question

Sono nuovo di Scheme, utilizzo Schema MIT da un po 'di tempo. Sto cercando di capire come implementare algoritmi di grafi popolari come gli algoritmi di percorso più brevi, BFS, DFS. Esistono tutorial che potrebbero aiutarmi a comprendere la ricorsione che sarebbe stata coinvolta, insieme alle strutture dati appropriate? Ho provato a usare Googling, ma questo non mi ha dato buoni risultati.

MODIFICA: Mi scuso per non essere più specifico in precedenza. La mia domanda riguardava attraversare l'intero grafico e non trovare il percorso tra uno obiettivo nodo. Quindi, dato un grafo G (V, E), dove V è l'insieme dei vertici e E rappresenta l'insieme degli archi, partendo da qualsiasi nodo n, qual è generato il percorso in modo che alla fine questa traversata, tutti i nodi sono visitati.

maggior parte delle implementazioni che ho trovato mentre Googling erano quelli con il inizio e obiettivo nodo. La mia versione (una delle risposte), sceglie un vertice e visita tutti gli altri.

Prendiamo ad esempio il seguente grafico: -

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

Questo DAG trovi (4-> 2), (2-> 3), (5-> 6) e (5-> 7), che non riesco a rappresentare nel diagramma. :-)

traiettoria percorsa a partire dal 1 potrebbe essere:

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

Answer 1

Abbiamo impiegato un po 'di tempo, ma finalmente ho funzionato! Il mio output è la sequenza in cui i nodi sarebbero stati visitati durante l'attraversamento attraverso DFS.

Nota che sto ancora imparando solo Scheme e il mio approccio alla programmazione potrebbe non essere il migliore.Se trovi qualcosa di sbagliato, errato o qualcosa che può essere espresso meglio, lascia un commento!

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

ingresso campione potrebbe essere: (DFS '((1 (2)) (2 (3)) (3) (4) (4 (2)) (5 ​​(3 6)) (6 ())))

Answer 2

in ampiezza e profondità prima ricerca sia si verificano come esempi in How To Design Programs, a partire dalla sezione 28. Penso che questo probabilmente ti aiuterà in modo più specifico con la tua domanda sugli usi della ricorsione nell'elaborazione del grafico.

Answer 3

Se rappresentate grafici come questo, cioè come un elenco di nomi dei nodi ei nomi dei loro vicini:

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

che ha il vantaggio che si può anche rappresentare i grafici ciclici senza ricorrere a modifiche distruttiva la struttura dei dati (set-cdr! ecc.), a condizione di consentire più voci nell'elenco per ciascuna chiave.

In alternativa, è possibile memorizzare non solo i nomi, ma la rappresentazione completa di ogni vicino in un elenco, in modo che si può camminare il grafico senza fare alcun ricerche di nomi:

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

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

Per fare un grafico ciclico questo comunque, dovresti usare set! o qualche variante. Quindi la migliore rappresentazione dipende davvero dall'applicazione.