这个问题可以在每个查询 O(n + m) 中轻松解决，但是这是否可以通过比 O(n²) 更好的预处理来以更好的复杂性回答此类查询？
在树中，可以通过使用预购和有序来轻松完成。我在 DAG 中尝试了类似的方法，但没有任何意义。
我也尝试将这个问题改成 LCA in DAG 问题，但是在 DAG 中找到 LCA 并不能足够快地解决。
准确地说，约束让我们说：
n - 顶点数，最多 10^5
m - 边数，最多 10^5
q - 查询数，最多 10^5
问问题
1765 次
4 回答
0
有趣的问题。我的直觉说“不”。不过我还没有想通。
但是（假设这个问题不是理论上的问题），出于实际目的，您可以使用Bloom filter。
使用布隆过滤器解决问题的一种可能方法是首先生成 K 个不同的图顺序，并为每个顺序存储从节点到其索引的映射。然后，为了测试从 N1 到 N2 的“可达性”，您检查（foreach 顺序）是否 index-of-N1 小于 index-of-N2（此检查为 O(1)）。如果这适用于所有订单，则可以以相当高的概率到达（假设 K 足够大）。（根据您的实际用例，偶尔产生这样的误报甚至可能是可以的，或者您可以运行可靠的 O(N+M) 检查）。否则，绝对不是。
于 2015-08-28T19:40:08.427 回答
0
我有一种感觉，可能会有一个解决方案，但这绝不是一个完整的解决方案。
令 S 为顶点的子集。对于图中的每个顶点 V，考虑集合 D_S(V)，我将其定义如下：如果 V 在 S 中，则 D_S(V) = {V}，否则，D_S(V) 是 {V} 与V 的所有直接后代 W 的集合 D_S(W)。（也就是说，它是“V 的所有最终后代，但只要遇到 V 的元素就停止递归”。）问题是：我们能找到一个集合S 使得 S 的大小为 O(f(N)) 并且 D_S(V) 对于所有 V 的大小为 O(g(N))，并且 f 和 g 是渐近亚线性的？（例如，也许我们可以同时实现两者的 sqrt。）
如果我们能找到这一点，那么我建议采用以下策略。对于预处理，为 S 中的每个 U 创建一个哈希表，其中包含最终可以从 U 到达的所有顶点。这可以在 O(f(N) * M) 中实现；这不一定比 O(N^2) 好，但至少比 O(M*Q) 好。
现在回答一个查询“U 是否可以从 V 到达？”，如果 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 的图必然具有我们可以利用的一定程度的一致性……或者可能没有。我不知道。任何想法，让我知道！
于 2015-09-05T20:39:35.103 回答
0
如果您正在考虑通过一些预处理来提供快速的多个 path_exists(src_vertex, dest_vertex) 查询，请考虑调用Warshall 算法来确定传递闭包，该闭包告诉有向图中的任意两个任意节点之间是否存在路径，作为预处理步骤（可能在服务器启动时）。该算法的最坏情况时间复杂度为 O(n^3)，空间复杂度为 O(n^2)，其中 n 是节点数。该算法的输出是一个 nxn 矩阵，如果在 node_i 和 node_j 之间存在路径，则 matrix[i][j] = 1，否则为零。因此，在查询服务时，您可以通过在传递闭包矩阵中查找 (i,j) 对，在 O(1) 时间内返回结果。
于 2021-09-25T15:26:03.597 回答
0
任何对 DAG 进行可达性查询的算法都可以通过压缩强连通分量来回答一般有向图上的此类查询。所以我不认为 DAG 条件对降低复杂性有任何作用。
至于有向图的可达性查询，本文提到的索引构建技术可能对某些情况有所帮助。
于 2020-12-03T04:37:51.400 回答