将图中的路径编码为字符串？

Question

假设我有一个 DAG，并且不使用图形数据库，而是将路径编码为

{id:"node3", path:"node0|node1|node2"}

来表示

node3

可以通过

node0

然后

node2

到达

node1

。如果读取不频繁，将路径编码在字符串中是个好主意吗？每条路径通常不包含超过 50 个节点。

谢谢

Answer 1

我认为你会发现你的方法不会如你所愿。使图变得有趣的属性之一是其结构中可能发生的“组合爆炸”。存储每个节点的每条路径将会变得非常快，我认为它将停止扩展并执行您期望的操作。 考虑以下博客文章：

http://thinkaurelius.com/2012/04/21/loopy-lattices/

http://thinkaurelius.com/2013/06/12/loopy-lattices-redux/

这些帖子探讨了 20x20 有向格的路径计数。它发现一个图“只有 441 个顶点和 840 个边，却拥有超过 1370 亿条唯一的有向路径。”