graph-theory - 有向无环图的 S 表达式？

Question

正如我们所知，树结构可以用 S 表达式表示。例如

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

但是是否可以将 S 表达式用于图形(尤其是 DAG)？例如



我的第二个问题是 S-expression 的拓扑极限可以表示什么？

我在谷歌上搜索了这个问题并找不到线索，没有正式的 CS 背景，我自己很难弄清楚。请不要关闭这个问题。提前致谢!

Answer 1

不像你的二叉树那样是递归结构。

您可以使用节点列表，并且对于每个存储节点，它都有一个边缘。

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

您可以存储节点和边的列表。

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