优化有向无环图中的连接查询

Question

3

这是我正在处理的个人项目之一。我有一个包含N个节点（例如一百万个）的DAG，我将查询两个节点的连通性[isConnected(a,b)]。我将在线查询DAG M次（例如一百万次）。有没有办法优化这个过程？

以下是我能想到的最佳方法：

BFS = O(M * N)

Dijkstra = O(M * E * log N)，其中E是图中边的数量。

是否有其他更好的方法来处理此过程？我目前正在使用第二种策略。这在我的系统中需要很长时间。

- Crusher

“querying” 你的意思是搜索吗？你想在这些树上执行什么操作？ - user2485710

这里是 Big-O 大O 表，其中包括搜索算法的时间复杂度。可能会有所帮助。 - user2485710

@user2485710 我将检查两个节点是否相连。使用任何一种模式都无法改善我从 Dijkstra 算法中得到的 O(M * E* logN) 的时间复杂度。 - Crusher

在 O(MElogN) 中，E 代表什么意思？ - notbad

查询是在线还是离线的。离线意味着在搜索之前您已知道所有的查询。在线意味着查询逐个来临，您事先不知道它们。 - notbad

@notbad 我已经编辑了问题。这是在线查询。但如果可以高效地离线完成，那也会为我打开一扇门。 - Crusher

4个回答

1

优化该过程的方法是生成一些辅助结构，以加快可达性查询。即使不考虑生成这些结构（或更新它们）的时间，也存在一个平衡点，即辅助结构的大小和查询速度之间的平衡。

在大规模图中的可达性查询：一种快速的精细在线搜索方法论文的介绍中已经很好地描述了这一点；该论文提出的方法是为每个顶点使用两个额外的数字。您可以在那里找到其他解决方案的参考。

- Jakub Narębski

0

根据您的图形大小，可能需要考虑一些大数据方法。也就是说，如果您的图形有几个千兆字节大，那么内存/磁盘访问将成为瓶颈，而不是CPU操作。

解决这种问题需要以某种方式对数据进行分组，使您只需加载一次数据。因此，您应该使您的数据结构可以分成适合内存并且可以一次性处理并且后续不需要进一步处理的块。

针对您的问题，其中一种大数据方法是将图形分成连接的子图，仅在这些子图上运行Dijkstra算法。然后，在此之后，您可以通过再次使用Dijkstra算法来检查每个子图是否实际连接（因为您有一个DAG）。但是，这需要预处理您的数据（一次），并且您的数据结构应该是相互靠近的子图内存块。

- invalid_id

0

您可以计算DAG的传递闭包，然后在常数时间内回答查询。但是，这需要高达O(n³)的时间和O(n²)的内存。有一些方法可以接受更长的查询时间以进行更快的预处理或更低的内存使用，例如请参见此演示文稿。

- Falk Hüffner

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mcdowella · Accepted Answer

我能看到一些加速，但通常无法高效地解决问题。

首先，将图视为无向图，并将其拆分为连通组件。不在同一连通组件中的两个点必须是断开的。

对于每个连通组件，再将其视为有向图，并将其拆分为强连通组件。在同一强连通组件中的两个点必须是连接的。

现在将每个连通组件视为节点的DAG，其中每个节点实际上是一个强连通组件。您可以对其进行拓扑排序。如果节点A在节点B的上游，则没有逆流路径从B到A。

您的DAG可能不是树，但如果是，则可以有效地解决最近公共祖先问题。从A到B的唯一路径向上到其最近公共祖先，然后再向下。如果这些路径都按正确的方向进行拓扑排序，则可以从A到B。

对于完全不同的方法，通过谷歌搜索可以找到许多快速计算大型网络中最短路径的算法。其中一些可能适用。