2

我需要找到作为所选节点的子节点的所有节点。图形是这样创建的： (setq graf1 '((A(BC)) (B(DE)) (C (FG )) (D (H)) (E(I)) (F(J)) (G( J)) (H()) (I(J)) (J()))) 所以，节点 B 的所有子节点都是（在第一级）D，E，在第二个 H，I，第三个 J。这是代码寻找第一级的孩子，但因为我是 lisp 的初学者，所以我不能让它适用于其他孩子。

(defun sledG (cvor graf obradjeni)
  (cond ((null graf) '())
        ((equal (caar graf) cvor)
                (dodaj (cadar graf) obradjeni))
        (t(sledG cvor (cdr graf) obradjeni)))
(defun dodaj (potomci obradjeni)
  (cond ((null potomci) '())
        ((member (car potomci) obradjeni)
         (dodaj (cdr potomci) obradjeni )
        (t(cons (car potomci)
                (dodaj (cdr potomci) obradjeni) ))))
(setq graf1 '((A(B C)) (B(D E)) (C (F G )) (D (H)) (E(I)) (F(J)) (G(J)) (H()) (I(J)) (J())))
4

2 回答 2

2

使用alexandria包：

(defvar *graf*
  '((a (b c)) (b (d e)) (c (f g)) (d (h)) (e (i)) (f (j)) (g (j)) (h nil) (i (j)) (j nil)))

(defun descendants (tree label)
  (let ((generation
         (mapcan #'cadr
                 (remove-if-not
                  (alexandria:compose (alexandria:curry #'eql label) #'car)
                  tree))))
    (append generation (mapcan (alexandria:curry #'descendants tree) generation))))

;; (D E H I J)

我相信，这就是你想要做的。这将适用于非循环图，但如果你有一个循环，它将“永远”重复出现。如果您想添加深度计数器，您可以通过插入深度计数器将其作为一个参数添加到descendants或在最后一次转换结果列表中。mapcan

包括深度：

(defun descendants (tree label)
  (labels ((%descendants (depth label)
             (let ((generation
                    (mapcan #'cadr
                            (remove-if-not
                             (alexandria:compose
                               (alexandria:curry #'eql label) #'car)
                             tree))))
               (append (mapcar (alexandria:compose
                                #'nreverse
                                (alexandria:curry #'list depth))
                               generation)
                       (mapcan (alexandria:curry #'%descendants (1+ depth))
                               generation)))))
    (%descendants 0 label)))

;; ((D 0) (E 0) (H 1) (I 1) (J 2))
于 2013-03-27T17:12:20.853 回答
2

当我阅读它时，该图是有向图。因此，要找到图的子项（有向边）（在示例中），

(defun children (node graph) (second (assoc node graph)))

然后

(children 'b graf1) ; with graf1 from the OP

返回 (DE)。那么你所要做的就是遍历孩子，比如（非常快速和肮脏）

(defun all-children (node graph)
  (let ((c (children node graph)))
    (if (null c) nil
        (union c (loop for x in c appending (all-children x graph))))))

这将返回 (JIHDE) 作为 B 的子项。

于 2013-03-27T10:37:09.723 回答