0
$\begingroup$

Connectivity in undirected graph can be easily identified using Disjoint Union Set (Union Find). Is there any way to check connectivity in a directed graph efficiently other than doing Depth First search or Breadth First Search? Is there any data structure that solves this problem efficiently.

For Example :

a -> b -> c
e -> b -> c

hasPath(a, c) => true
hasPath(e, c) => true
hasPath(e, a) => false
hasPath(c, a) => false
$\endgroup$
8
  • $\begingroup$ How much preprocessing time is allowed? With $O(n^2)$ preprocessing you can answer queries in $O(1)$ time. $\endgroup$ Commented Sep 5, 2021 at 11:03
  • $\begingroup$ preprocessing is fine as long as the the memory does not exceed O(n). O(n) or O(n log n) time is preferred. $\endgroup$ Commented Sep 5, 2021 at 11:18
  • $\begingroup$ What is the problem with BFS\DFS? $\endgroup$
    – nir shahar
    Commented Sep 5, 2021 at 11:20
  • $\begingroup$ @nirshahar Consider a graph with million nodes. For multiple queries each query consumes O(n) time which is costly. $\endgroup$ Commented Sep 5, 2021 at 11:22
  • 1
    $\begingroup$ @VeeraKumar Could you please edit your question and mention your requirements as discussed in the comment section above. $\endgroup$ Commented Sep 5, 2021 at 19:36

1 Answer 1

2
$\begingroup$

The problem that you stated is known as the Graph Reachability Query problem. You may want to check this paper: An Efficient Algorithm for Answering Graph Reachability Queries, and the references therein.

The paper discusses the previously known results as well as optimizes both on the space complexity and the query complexity. The algorithm takes $O(n^2 + bn \cdot \sqrt{b})$ pre-processing time and $O(bn)$ space, where $b$ is the width of the graph, defined as the size of the largest subset $U$ of $V$ such that for every pair of nodes $u, v \in U$, there does not exist a path from $u$ to $v$ or from $v$ to $u$. The query complexity of the algorithm is $O(\log b)$.

Note that the value of $b$ could actually be $\Theta(|V|)$, for example, take a star graph on $n$ vertices. Therefore, the algorithm might be more useful for dense graphs, for which $b$ is usually small.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.