Şemada grafik programlama

Question

Şimdiye kadar bir süredir MIT Scheme kullanıyordum. En kısa yol algoritmaları, BFS, DFS gibi popüler grafik algoritmalarının nasıl uygulanacağını anlamaya çalışıyorum. İlgili veri yapıları ile birlikte yer alacak olan yinelemeyi anlamada bana yardımcı olabilecek eğiticiler var mı? Googling'i denedim, ama bu bana iyi sonuçlar vermedi.

EDIT: Daha erken olmadığından dolayı özür dilerim. Sorum, tüm grafiğin geçişini yapmak ve başlangıç ​​ ve hedefi düğümü arasındaki yolu bulmayla ilgili değildi. Bu yüzden, herhangi bir düğüm N başlayarak kenar seti V tepe grubu ve E bir grafik G (V, E), aşağıda sunulmuştur, yol oluşturulur ne sonunda, böylece Bu geçiş, tüm düğümler ziyaret edilir. Googling ederken buldum

Çoğu uygulamalar başından ve gol düğüm ile olanlardı. Benim versiyonum (cevaplardan biri), bir köşe noktası seçer ve diğerlerini ziyaret eder. örneğin

al, aşağıdaki grafik: -

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

Bu DAG (5- (4-> 2), (2-> 3), (> 6 5-) vardır ve> 7), diyagramda temsil edemedim. :-)

Yol itibaren Traversed olabilir:

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

Answer 1

Biraz zaman aldım, ama sonunda çalışıyorum. Çıktım, düğümlerin DFS aracılığıyla geçiş sırasında ziyaret edileceği dizidir.

Yalnızca şema öğreniyorum ve programlama yaklaşımım en iyi olmayabilir.Yanlış, yanlış veya daha iyi ifade edilebilecek bir şey bulursanız, yorum bırakın!

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

Örnek girdisi olabilir: (DFS '((1 (2)) (2 (3)) (3 (4)) (4 (2)) (5 ​​(3 ila 6)) (6 ())))

Answer 2

Genişlik birinci ve derinliği birinci hem arama 28 bölümünden başlayan How To Design Programs örneğinde ortaya çıkar. Bu, özellikle grafik işlemede özyinelemenin kullanımıyla ilgili sorunuzda size yardımcı olacaktır.

Answer 3

Eğer düğüm isimlerinin listesi olarak yani böyle grafikler ve komşularının adlarını temsil ederse: hatta yıkıcı modifikasyon başvurmadan halkalı grafikleri temsil edebilir avantajı

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

Veri yapınız (set-cdr! vb.), her bir anahtar için listede birden çok girişe izin verdiğiniz sürece.

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

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

döngüsel grafik bu yapmak için: Eğer herhangi bir ad aramalarını yapmadan grafiği yürüyebilir böylece

Alternatif olarak, adları ancak listedeki her komşu tam temsilini sadece depolayabilir Ancak, set! veya bazı varyantları kullanmanız gerekir. Bu yüzden en iyi temsil gerçekten uygulamaya bağlıdır.