问如何将有向无环图(DAG)存储为JSON？

EN

标记每个节点，并制作一个边列表。也就是说，对于每个节点，存储它具有边的节点，例如：

{
  "a": [ "b", "c", "d" ],
  "b": [ "d" ],
  "c": [ "d" ],
  "d": [ ]
}

您可以通过这种方式存储许多类型的图，而不仅仅是DAG，因此您需要对其进行后处理，以确保它没有循环。如果您多次看到某个节点不是DAG，只需选择一个节点DFS即可。然后删除您刚才看到的所有节点，并对剩余的节点重复上述操作。一直执行此操作，直到找到一个循环或删除了所有节点，在后一种情况下，图形为DAG。

请注意，这不会存储父节点，因为这是冗余信息。如果需要这些数据，您可以在加载图形后生成这些数据。

JSON没有表示DAG的原生工具，除非您制定自己的约定来表示链接数据。JSON-LD (一个W3C提议)就是一个试图做到这一点的JSON扩展。该提案可以在这里找到：http://json-ld.org/spec/latest/json-ld/。