优化连接查询，在向非循环图 [英] Optimizing connectivity queries in a Directed Acyclic Graph

问题描述

这是我的工作对个人的项目之一。我有N个节点（比如亿美元），我会在查询两个节点连接的DAG [isConnected（A，B}。我会查询DAG在线M（比如亿美元）次。有没有办法来优化流程？

This is one of the personal projects that I am working on. I have a DAG of N nodes ( say million ) that I will querying for connectivity of two nodes [ isConnected(a,b} ]. I will be querying the DAG online M ( say million ) times. Is there a way to optimize the process?

下面是我能想出的最好的办法。

Here are the best approaches that I could come up with.

BFS = O（M * N）

BFS = O( M * N )

Dijkstra算法= O（M * E *日志N），其中E为图中的边数。

Dijkstra = O( M* E* log N) where E is the number of edges in the graph.

是否有这个过程的任何其他更好的方法？我现在使用的第二个策略。这需要永远留在我的系统。

Is there any other better approach for this process ? I am right now using the second strategy. This takes forever in my system.

推荐答案

可以计算出传递闭包的DAG，然后回答在固定时间内的查询。然而，这需要高达O（n³）时间和O（N²）内存。有迹象表明，接受较长的查询时间更快preprocessing或更低的内存使用的一些方法，如见这presentation 。

You can calculate the transitive closure of the DAG and then answer the queries in constant time. However, this requires up to O(n³) time and O(n²) memory. There are some methods that accept longer query times for faster preprocessing or lower memory use, see e.g. this presentation.

这篇关于优化连接查询，在向非循环图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！