用通用Lisp表示有向无环图

Question

通常，为了在Lisp中表示一个基本的无向图，我可以创建一个父节点和它们对应的子节点的列表，正如本问题中所讨论的那样（为了方便起见，下面举例说明）。

这张图给出了一个边列表：

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

这适用于树或任何其他无向图的情况。然而，当我们想要表示一个有向无环图时，这种类型的表示就会崩溃，其中每个节点可以有多个父节点：

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

Answer 1

表示DAG的正确方法是节点（顶点）的集合：

(defstruct node
  payload
  children)

由于结构只有两个插槽，所以当然可以使用cons单元格。

您给出的树的列表表示将有效负载与无子节点混为一谈，并将最右边的分支弄乱。正确的表示形式是

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

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

(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)))