Search for reachable vertices for each vertex in a directed graph

Question

I know that the brute force approach for this runs DFS at all vertices of the graph. Therefore, for this algorithm, the complexity will be O (V | V + E |). But is there a more efficient way to do this?

Answer 1

I get the impression from documents like http://research.microsoft.com/pubs/144985/todsfinal.pdf that there is no algorithm that is better than O(VE) or O(V^3) in the general case. For sparse graphs and other special graphs, faster algorithms exist. It seems, however, that you can still improve by separating the "index construct" from the "query" if you have an idea of ​​the number of queries that will be made in the data. If there will be many queries, O(1) is possible for queries if all the data is precomputed (DFS or Floyd-Warshall, etc.) and stored in O(n^2) space. On the other hand, if there are relatively few queries, the time to build the space and / or index can be reduced due to the query time.

Answer 2

I really suspect that there is no known best algorithm for general graphs. All the documents I found on this subject [1] [2] describe algorithms that work in O (| V | * | E |). This is no better than your naive attempt at worst.

Even the wikipedia page [3] says that the fastest algorithms reduce the problem to matrix multiplication, and the fastest algorithms are only slightly better than the original ones.

[1] http://ion.uwinnipeg.ca/~ychen2/conferencePapers/tranRelationCopy.pdf

[2] http://www.vldb.org/conf/1988/P382.PDF

[3] http://en.wikipedia.org/wiki/Transitive_closure#Algorithms

Answer 3

[EDIT: As noted by Kraskevich, the final step of the query may be worse than I originally stated: up to O (| V | ^ 2) even to output the size of O (| V |), which is no better than regular DFS without any preprocessing. ] .

In the worst case, the space O (| V | ^ 2) is required to store all this information explicitly, i.e. keep a complete list of reachable vertices for each vertex (think of a graph in which each vertex has an edge for each other vertex). But you can imagine it in such a way that only the space O (| V |) is required, and this representation can be built in O (| V | + | E |) time , and the request for it will only be time proportional to the size of the response ( number of reachable vertices) .

Main idea: Each vertex in a strongly connected component (SCC) can reach any other vertex in the same SCC (this is the definition of SCC) and can reach all the vertices in the SCC that it can reach and other vertices.

• Find all SCC; this can be done in O (| V | + | E |). Create an SCC table, so SCC (u) = i if SCC is from u is i (both vertices in G and SCC can be represented as integers). Then go through this table one more time to create a double Verts table, so that Verts (i) contains a list of all the vertices in the ith SCC.
• We construct a new graph G 'whose vertices are SCC G. G' will necessarily be acyclic.

So, given the vertex u in G, find its SCC, SCC (u). Call it i. Run DFS through G 'starting at vertex i: for each vertex (from G') j encountered during this DFS, output each vertex (from G) to Verts (j).