[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/mgrPcZel    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Apr 3:
; 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))


Output:
1
((9 E G) (5 C E) (7 B E) (7 A B) (6 D F) (5 A D))


Create a new paste based on this one


Comments: