codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; minimum spanning tree: prim's algorithm (define (remove x xs) (let loop ((xs xs) (zs '())) (cond ((null? xs) (reverse zs)) ((equal? (car xs) x) (loop (cdr xs) zs)) (else (loop (cdr xs) (cons (car xs) zs)))))) (define (min es t r) (let loop ((es es) (min-e #f) (min-c #f)) (cond ((null? es) min-e) ((or (and (member (cadar es) r) (member (caddar es) r)) (and (member (cadar es) t) (member (caddar es) t))) (loop (cdr es) min-e min-c)) ((or (not min-c) (< (caar es) min-c)) (loop (cdr es) (car es) (caar es))) (else (loop (cdr es) min-e min-c))))) (define (prim vs es) (let loop ((t (list (car vs))) (r (cdr vs)) (mst '())) (if (null? r) mst (let* ((e (min es t r)) (v (if (member (cadr e) t) (caddr e) (cadr e)))) (loop (cons v t) (remove v r) (cons e mst)))))) (define vertices '("A" "B" "C" "D" "E" "F" "G")) (define edges '((5 "A" "D") (7 "A" "B") (9 "B" "D") (8 "B" "C") (5 "C" "E") (7 "B" "E") (15 "D" "E") (6 "D" "F") (8 "E" "F") (9 "E" "G") (11 "F" "G"))) (display (prim vertices edges))
Private
[
?
]
Run code
Submit