用公共Lisp表示有向无环图

表示DAG的正确方法是 (顶点):

(defstruct node
  payload
  children)

cons 而不是细胞。

所给树的列表表示形式 合并 有效载荷 带着一个没有孩子的孩子 节点 把最右边的树枝弄乱了。 正确的表示是

(1 (2 (6) (7) (8)) (3) (4 (9 (12))) (5 (10) (11)))

现在,共享无子节点的DAG (8) 在孩子们之间 节点数 (2 ...) 和 (3 ...) 应该只共享一个单元:

(1 (2 (6) (7) #1=(8)) (3 #1#) (4 (9 (12))) (5 (10) (11)))

看到了吗 #n= #n# 对于读者来说。 当然,你不应该用它们来 达格。

下面是创建DAG的方法:

(defun make-node (&key payload children)
  (cons payload children))
(defparameter *my-dag*
  (let ((shared-mode (make-node :payload 8)))
    (make-node
     :payload 1
     :children
     (list (make-node :payload 2
                      :children (list (make-node :payload 6)
                                      (make-node :payload 7)
                                      shared-mode))
           (make-node :payload 3
                      :children (list shared-mode))
           (make-node :payload 4
                      :children (list (make-node :payload 9
                                                 :children (list (make-node :payload 12)))))
           (make-node :payload 5
                      :children (list (make-node :payload 10)
                                      (make-node :payload 11)))))))
(setq *print-circle* t)
*my-dag*
==> (1 (2 (6) (7) #1=(8)) (3 #1#) (4 (9 (12))) (5 (10) (11)))

只需列出具有两个节点ID的顶点:

((1 2) (1 3) (1 4) (1 5) (2 6) (2 7) (2 8) ... )

或者使用向量:

#((1 2) (1 3) (1 4) (1 5) (2 6) (2 7) (2 8) ... )

或者使用节点及其后续节点的列表:

((1 2 3 4 5) (2 6 7 8) (3 8) (4 9) ...)