PROSAGA码农传奇-lisp-在Common Lisp中表示有向无环图

在Common Lisp中表示有向无环图

作者: 布偶的表弟派大星丶
发布时间: 2024-12-31 08:49:29 (16天前)
转自：

<div class =“post-text”itemprop =“text”>
  
    表示DAG的正确方法是
    
      节点
    
     （顶点）：
  
   <pre>
 <code>
 (defstruct node
 payload
 children)

</code>
 </pre>
  
    由于结构只有两个插槽，当然可以使用

<a href="http://clhs.lisp.se/Body/t_cons.htm" rel="nofollow noreferrer">
       <code>
 cons
 </code>
    </A>
     而是细胞。
  
  
    您提供的树的列表表示
合并了
    
      有效载荷
    
     没有孩子
    
      节点
    
    
并弄乱了最右边的分支。
正确的表示是
  
   <pre>
 <code>
 (1 (2 (6) (7) (8)) (3) (4 (9 (12))) (5 (10) (11)))

</code>
 </pre>
  
    现在，共享无子节点的DAG
     <code>
 (8)
 </code>
     孩子之间
节点
     <code>
 (2 ...)
 </code>
     和
     <code>
 (3 ...)
 </code>
     应该只分享细胞：
  
   <pre>
 <code>
 (1 (2 (6) (7) #1=(8)) (3 #1#) (4 (9 (12))) (5 (10) (11)))

</code>
 </pre>
  
    看到
    <a href="http://clhs.lisp.se/Body/02_dho.htm" rel="nofollow noreferrer">
       <code>
 #n=
 </code>
    </A>
     和

<a href="http://clhs.lisp.se/Body/02_dhp.htm" rel="nofollow noreferrer">
       <code>
 #n#
 </code>
    </A>
     对于读者记谱法。
当然，你不应该使用它们
    
      创建
    
     DAG的。
  
  
    以下是创建DAG的方法：
  
   <pre>
 <code>
 (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)))

</code>
 </pre>
</DIV>