# Connectivity in Directed Graph

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

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

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.