有向无环图的S表达式？

Question

我们知道，树形结构可以用S表达式来表示。例如：

 (5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )

但是，能否将S表达式用于图形（特别是DAG）？例如：

我的第二个问题是S表达式可以表示的拓扑限制是什么？

我搜索了这个问题，但没有找到答案。由于我没有正式的计算机科学背景，我自己很难弄清楚这个问题。请不要关闭此问题。先感谢您！

- est

Answer 1

不像您的二叉树那样作为递归结构。

• You could use a list of nodes, and for each store which nodes it is has an edge to.

  ( (2 ())
    (3 (8 10))
    (5 (11))
    (7 (8 11))
    (8 (9))
    (9 ())
    (10 ())
    (11 (2 9 10)) )
  

• You could store a list of nodes and edges.

  ( (2 3 5 7 8 9 10 11)
    ( (3 8)
      (3 10)
      (5 11)
      (7 8)
      (7 11)
      (8 9)
      (11 2)
      (11 9)
      (11 10) ) )
  

- Markus Jarderot

---

很酷，谢谢。我在谷歌上搜索了一些生成树的解决方案，还在尝试理解。 - est

对于有向图而言，生成树没有多大意义。你至少需要针对每个源节点（3、5、7）创建一个生成树。 - Markus Jarderot