data-structures - 在图上定义无效路径

Question

我们正在开发一个适合大多数情况的常规有向图的项目。然而，在我们的图表上，我们想要使一些路径无效。例如，如果我们的图表是：

A->B
A->D
B->C
D->C

那么 A->B->C 是有效路径，但 A->D->C 不是。我们可以在某处定义无效路径并每次都进行验证检查，但这会导致一个重要的性能问题，因为我们的应用程序高度依赖于图。

那么，对于这种类型的情况，是否有特殊的数据结构或算法？

谢谢

Answer 1

您可以在的每个节点上存储一个映射，from:list(to)这样您就知道来自 A 的路径不能到达 C，因为它不在可以从 C 到达的节点列表中。如果深度大于 1，则通向它的节点元组可以是一个键而不是那个节点。这很像 eBGP 用于 Internet 路由的方式。

另一方面，如果您决定使用您所描述的数据结构，无论如何您都需要进行检查。要么，要么为每种情况存储多个图表。