gpt4 book ai didi

graph - 在 Common Lisp 中表示有向无环图

转载 作者:太空宇宙 更新时间:2023-11-03 18:45:04 25 4
gpt4 key购买 nike

通常,为了在 Lisp 中表示一个基本的无向图,我可以创建一个父节点列表及其对应的子节点,如 this question 中所讨论的那样。 (为方便起见,如下图所示)。

enter image description here

这个图产生了一个边列表:

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

这适用于树或任何其他无向图的情况。然而,当我们想要表示每个节点可以有多个父节点的有向无环图时,这种表示就失效了:

enter image description here

现在,节点 8 有多个父节点 (2、3),但是当我们试图表示这一点时,我们无法判断节点 8 是否连接到两个父节点,或者是否有两个节点 8:

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

在具有唯一节点的图的情况下,我们当然可以做出这个假设,但据我所知,DAG 可以有重复的节点……那么我们如何处理这个问题呢?此外,我们如何在 Lisp 中将其表示为列表?

最佳答案

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

(defstruct node
payload
children)

由于结构只有两个插槽,当然可以使用一个, cons细胞代替。

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

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

现在,在子节点之间共享无子节点 (8) 的 DAG节点 (2 ...)(3 ...) 应该只共享单元格:

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

参见 #n=#n#为读者记法。当然,您不应该使用它们来创建 DAG。

下面是创建 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)))

关于graph - 在 Common Lisp 中表示有向无环图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52209509/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com