3

我试图表示一个传递关系（在数据库中）并且很难找出最好的数据结构。

基本上，数据结构是一系列对A → B，例如 ifA → B和B → C, then 隐含A → C。能够识别哪些条目是原始输入以及哪些条目是隐式存在的，这对我来说很重要。询问是否A → C相当于我有一个有向图并询问该有向图中是否存在从A到的路径C。

我可以只表示原始条目，但如果我这样做，则需要花费大量时间来确定两个项目是否相关，因为我需要搜索所有可能的路径，这相当慢。

或者，我可以存储原始边缘以及所有路径的列表。这使得添加新边变得容易，因为当我添加时，A → B我可以将路径结尾的笛卡尔积和路径结尾A的路径B放在一起。在最坏的情况下，这具有 O( n 2 ) 的一些显着空间开销，但具有很好的属性，即查找，迄今为止最常见的操作，将是恒定时间。问题是删除，除了重新计算所有可能穿过或不穿过边缘的路径之外，我真的想不出任何东西，这真的很讨厌。

有没有人有更好的想法？

技术说明：有向图可能是循环的，但关系是自反的，所以我不需要表示自反或存储任何关于它的东西。

4

1 回答 1

1

这称为可达性问题。

看起来你想要一个高效的在线算法，这是一个开放的问题，也是一个需要大量研究的领域。

请参阅我在cs.SE上的类似问题：DAG 的增量压缩传递减少，具有有效的可达性查询，其中我在 stackexchange 中引用了几个相关的问题：

有关的：

请注意，即使某些算法可能仅适用于 DAG，但如果它支持压缩（即，将强连接的组件折叠到一个节点，因为它们被认为是相等的，即它们来回关联），它是等价的；压缩后，您可以在图中查询代表节点来代替任何压缩节点（因为它们都可以相互访问，因此以完全相同的方式与图的其余部分相关）。

我的结论是，到目前为止，似乎还没有一种有效的方法来做到这一点（对于动态图的 O(log n) 查询，在压缩图上具有输出敏感的更新时间）。对于效率较低的方法，请参阅上面的相关链接。

我发现的最接近的实用算法在这里（来源），这是一本有趣的书。我不确定这种数据结构或您会发现的任何论文中的任何数据结构有多容易/实用，它将使其适应数据库。

PS。考虑以后在cs.stackexchange.com上询问与 CS 相关的问题。

于 2013-10-15T22:59:37.217 回答