Прокомментировать код - Lisp (229547)

Формулировка задачи:

Добрый вечер, можете пожалуйста прокомментировать сей чудесный код (автор -

Catstail

) более подробно?

                    Листинг программы
                
 
                            
                        
;; Проверить ребро
 
(defun chk-vert (v s)
  (let ((a1 (car v))
        (a2 (cadr v)))
    (not (forsome s (lambda (w) (and (member a1 w) (member a2 w)))))))
        
;; Добавление очередного ребра в "лес"        
        
(defun ins-vert (v w)        
  (let* ((a1 (car v))
         (a2 (cadr v))
         (w1 (car (remove-if-not (lambda (x) (member a1 x)) w)))
         (w2 (car (remove-if-not (lambda (x) (member a2 x)) w))))
    (cond ((and (null w1) (null w2)) (cons (butlast v) w))
          ((null w1) (cons (cons a1 w2) (remove-if (lambda (x) (member a2 x)) w)))
          ((null w2) (cons (cons a2 w1) (remove-if (lambda (x) (member a1 x)) w)))
          (t (cons (append w1 w2) (remove-if (lambda (x) (or (member a1 x) (member a2 x))) w))))))
 
;; Очередной шаг
    
(defun action (graph &optional (w nil) (r nil))
  (cond ((null graph) r)
        ((chk-vert (car graph) w) (action (cdr graph) (ins-vert (car graph) w) (append r (list (car graph))))) 
        (t (action (cdr graph) w r))))
        
(defun kruskal (graph)
  (let ((g (qsort-a graph (lambda (x) (nth 2 x)))))
     (action g)))

P.S.: Реализация алгоритма Краскала (Крускала) - поиск минимального остовного дерева графа.

Решение задачи: «Прокомментировать код»

Листинг программы

;; Проверить ребро
 
(defun chk-vert (v s) ;; s - набор ребер уже включенных в каркас. v - очередное проверяемое ребро
  (let ((a1 (car v)) ;; начало v
        (a2 (cadr v))) ;; конец v
    ;; далее проверяется, не содержатся ли обе вершины v в одном из "островов" каркасе s
    ;; если содержатся - это ребро включать нельзя, т.к. возникнет цикл
    (not (forsome s (lambda (w) (and (member a1 w) (member a2 w)))))))
        
;; Добавление очередного ребра в "лес"        
        
(defun ins-vert (v w)    ;; v - ребро, w - текущий каркас (лес, набор ребер).    
  (let* ((a1 (car v)) ;; начало v
         (a2 (cadr v)) ;; конец v
         (w1 (car (remove-if-not (lambda (x) (member a1 x)) w))) ;; w1 - вершина из каркаса, соединенная с началом v 
         (w2 (car (remove-if-not (lambda (x) (member a2 x)) w)))) ;; w2 - вершина из каркаса, соединенная с концом v 
    (cond ((and (null w1) (null w2)) (cons (butlast v) w)) ;; если w1 и w2 = nil, просто присоединяем ребро (без длины) к каркасу
          ((null w1) (cons (cons a1 w2) (remove-if (lambda (x) (member a2 x)) w))) ;; присоединяем к верш. w1
          ((null w2) (cons (cons a2 w1) (remove-if (lambda (x) (member a1 x)) w))) ;; присоединяем к верш. w2
          (t (cons (append w1 w2) (remove-if (lambda (x) (or (member a1 x) (member a2 x))) w)))))) ;; объединение двух несвязанных "островов" добавляемым ребром в единый остров
  
;; Очередной шаг
    
(defun action (graph &optional (w nil) (r nil))
  (cond ((null graph) r) ;; если граф пуст - каркас сидит в r
          ;; если очередное ребро графа не приведет к циклу, добавляем его к каркасу,
          ;; а из графа при след. рекурсивном вызове исключаем
        ((chk-vert (car graph) w) (action (cdr graph) (ins-vert (car graph) w) (append r (list (car graph))))) 
        ;; если ребро нельзя добавлять - пропускаем
        (t (action (cdr graph) w r))))
        
;; Ведущая программа:
 
(defun kruskal (graph)
  (let ((g (qsort-a graph (lambda (x) (nth 2 x))))) ;; сортируем ребра по возрастанию длин 
     (action g)))  ;; и запускаем action...

Объяснение кода листинга программы

chk-vert - это функция, которая проверяет, можно ли добавить очередное ребро в каркас. Если оба конца ребра уже присутствуют в одном из островов каркаса, ребро не добавляется, чтобы избежать создания цикла.
ins-vert - это функция, которая добавляет очередное ребро в каркас. Если оба конца ребра уже присутствуют в каркасе, ребро не добавляется. Если один или оба конца отсутствуют в каркасе, они добавляются в соответствующую вершину.
action - это функция, которая выполняет очередной шаг алгоритма. Если граф пуст, возвращается текущий каркас. Если очередное ребро не приводит к циклу, оно добавляется в каркас и исключается из графа для следующего рекурсивного вызова. Если ребро приводит к циклу, оно пропускается.
kruskal - это ведущая программа, которая использует функцию action для обработки графа. Сначала граф сортируется по возрастанию длин ребер, а затем передается в функцию action для обработки.