检查是否可以从 DG 中的节点 S 到达节点 T

Question

在无向图中，很容易将图预先划分为组件并用标识组件的数字标记它们。因此，如果它们都具有相同的标签，则检查是否可以通过 S 的路径到达节点 T 为真。

是否可以在有向图中做类似的事情？基本上，预先计算然后做一个简单的查找是否可以在没有任何类型的 DFS 的情况下从 S 到达 T？

Answer 1

除了最简单的可达性矩阵实现及其优化（其复杂度为 O(n^2)。恐怕没有恒定时间查找。

虽然有一些有趣的想法。我将在下面列出其中两个：

1) 找到一组覆盖原始图G的树。使得 $1$

每个顶点V的索引如下：

For each t_i in T

    V is indexed by (t_i, a, b) where a is the smallest postorder of descendants in the tree and b is the postorder of V in the tree.

为了查询reach(u, v)，我们要查找是否存在一对(t_i, a_u, b_u) 和 (t_i, a_v, b_v) 这样 u_a <= v_b < u_b。详情请看

R. Agrawal, A. Borgida, and H. V. Jagadish. Efficient management of transitive relationships in large data and knowledge bases. In Proceedings of the 1989 ACM SIGMOD international conference on Management of data (SIGMOD 1989), 1989.

然后问题简化为如何找到覆盖图 G 的树 T 的最小集合。有多种方法可以做到这一点。

2) 另一种方法是 n-hop（参见 SODA 02 出版物）

Reachability and distance queries via 2-hop labels by Edith Cohen,Eran Halperin,Haim Kaplan,Uri Zwick

Let G = (V, E) be a directed graph. 
For v in V
    L(v) = (L_in(v), L_out(v)), such that L_in(v), L_out(v) ⊆ V and there is a path from every x ∈ L_in(v) to v and from v to every x ∈ L_out(v).

然后问题就简化为寻找最佳的 2 跳覆盖

Let G = (V, E) be a graph. For every u, v ∈ V , let P_uv be a collection of paths from u to v (for undirected graphs we have P_uv ≡ P_vu). Let P = {P_uv}. We define a hop to be a pair (h, u), where h is a path in G and u ∈ V is one of the endpoints of h. We refer to u as the handle of the hop. A collection of hops H is said to be a 2-hop cover of P if for every u, v ∈ V such that Puv 6= φ, there is a path p ∈ Puv, and two hops (h1, u) ∈ H and (h2, v) ∈ H, such that p = h1h2, i.e., p is the concatenation of h1 and h2. The size of the cover is |H|, the number of hops in H.

检查是否可以从 DG 中的节点 S 到达节点 T

Check if node T can be reached from node S in a DG

graph

dijkstra

graph-algorithm