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

Question

我想将 DAG 表示为 JSON 文本，并想知道是否有人尝试过这个，以及他们在验证 JSON 是否实际上是 DAG 时遇到的任何问题。

Answer 1

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

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

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

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