这个问题可以很容易地在O(n+m)每次查询中解决，但是有没有可能通过预处理获得比O(n²)更好的复杂度来回答这样的查询？
在树中，通过使用先序遍历和中序遍历可以很容易地完成此操作。我尝试在有向无环图（DAG）中进行类似的操作，但它没有意义。
我还尝试将这个问题转换为DAG问题中的LCA，但是在DAG中找到LCA并不能快速解决。
为了精确约束，假设：
n - 顶点数，最多为10^5
m - 边数，最多为10^5
q - 查询数，最多为10^5
4个回答
0
有趣的问题。我的直觉是“不行”。不过我还没有仔细思考过。
然而（假设这个问题不是理论性的），为了实际目的，您可以使用Bloom filter。
使用 Bloom filter 解决您的问题的一个可能方案是，首先生成 K 种不同的图形顺序，并为每个顺序存储从节点到其在该顺序中的索引的映射。然后，要测试从 N1 到 N2 的“可达性”，您需要检查（对于每个顺序）index-of-N1 是否小于 index-of-N2（此检查为 O(1)）。如果所有顺序都满足这个条件，则具有相当高的概率是可达的（假设 K 足够大）。 （根据您的实际用例，偶尔生成这样的误报可能是可以接受的，或者您可以运行可靠的 O(N+M) 检查）。否则，它肯定不可达。
- shx2
0
我有一种感觉，可能有以下解决方案，但这绝不是完整的解决方案。
设S为顶点的子集。对于图中的每个顶点V，考虑定义为D_S(V)的集合，如下所示：如果V在S中，则D_S(V)={V}，否则，D_S(V)是V的所有直接后代W的集合D_S(W)与{V}的并集。（也就是说，它是“V的所有最终后代，但每当你遇到V的元素时停止递归”。）问题是：我们能否找到一个集合S，使得S的大小为O(f(N))，且对于所有V，D_S(V)的大小为O(g(N))，其中f和g是渐近亚线性的？（例如，我们可以同时实现sqrt。）
如果我们能找到这个集合S，那么我建议采用以下策略。对于预处理，为S中的每个U创建一个哈希表，其中包含从U最终可达的所有顶点。这可以在O(f(N)*M)内完成；这不一定比O(N^2)更好，但至少比O(M*Q)更好。
现在来回答一个问题“从V能否到达U？”，如果V在S中，那么这很简单。否则，我们检查V是否等于U，在这种情况下也很简单。最后，我们递归地将相同的过程应用于V的所有后代，如果答案通过上述两种情况之一为“是”，则返回“是”，但只有当我们永远找不到U时才返回“否”。这个递归需要O(g(N))步骤。
剩下的问题是如何选择S。我认为，如果图形源自某个过程，其中出度遵循幂律，则可以选择具有最高出度的sqrt(N)个顶点。但例如，如果我们有N=2*K个顶点（i，0）和（i，1）的图形，其中K^2条边：从每个（i，0）到每个（j，1）；那么就没有合适的子集S。但是，也许没有适当的S的图表必然具有我们可以利用的均匀度量……或者也许没有。我不知道。有任何想法，请告诉我！
- Erik P.
0
任何用于有向无环图 (DAG) 上的可达性查询算法，都可以通过压缩强连通分量在一般有向图上回答这种查询。因此，我认为 DAG 的条件对于减少复杂度并没有什么作用。
至于有向图上的可达性查询，this paper 中提到的索引构建技术可能对某些情况有所帮助。
- Adder
0
如果您正在寻求用一些预处理来快速处理多个 path_exists(src_vertex, dest_vertex) 查询，请考虑调用 Warshall 算法以确定可达闭包，该算法告诉我们在有向图中是否存在任意两个节点之间的路径，作为预处理步骤（可能在服务器启动时）。该算法的最坏时间复杂度为 O(n^3)，空间复杂度为 O(n^2)，其中 n 是节点数。该算法的输出是一个 nxn 矩阵，其中 matrix[i][j] = 1 表示节点 i 和节点 j 之间存在路径，否则为零。因此，在查询服务时间，您只需通过在可达闭包矩阵中查找 (i,j) 对来以 O(1) 的时间返回结果即可。
- eternal_learner
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
O(n^2)的边（除非给定图是稀疏的），因此您正在寻找次线性时间...而“这个问题可以很容易地在O(n)中解决”不行，原因相同。 - amit