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

Question

这是我正在从事的个人项目之一。我有一个 N 节点(比如百万)的 DAG，我将查询两个节点 [isConnected(a,b}) 的连接性。我将在线查询 DAG M(比如百万)次。有没有办法优化过程？

这是我能想到的最佳方法。

最大优先级 = O( M * N )

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

这个过程还有其他更好的方法吗？我现在正在使用第二种策略。这在我的系统中需要很长时间。

Answer 1

我可以看到一些加速，但我不能在一般情况下有效地解决问题。

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

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

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

您的 DAG 可能不是一棵树，但如果是，您可以有效地解决它的最低公共(public)祖先问题。从 A 到 B 的唯一路径向上到达其最低的共同祖先，然后再次向下。如果这两条路线都在正确的拓扑排序方向上，那么您可以从 A 到达 B。

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