Finding reachable vertices in directed graph

user_7201420 0
Viewed 2553

I'd like to ask about the following problem:

Given a directed graph (not necessarily a DAG), for every vertex v calculate the number of reachable vertices from v.

So using brute force approach (n times DFS) we can get the answer in O(n^2) time complexity. Is there a way to calculate it faster? I can definitely make a DAG from the given graph using SCC. I tried to use previously calculated values, so I could visit each vertex only once, but it does not work at all. The biggest problem lies in a graph like this:

  2 -> 1
  3 -> 2
  3 -> 1
  1 -> 4

I run a DFS from vertex 1 and return result 1. Then, using it I can immidiately calculate answer for 2 (I do not enter vertex 1 again in second DFS, I use its answer instead), what is 2. Then I get to the vertex 3, and... the algorithm would sum up the result of 1 and 2, since I can reach both of those vertices. But vertex 1 is already calculated in the result for vertex 2. In that way I get the answer equal to 4, which is not true.

graph-algorithm graph algorithm
2 Answers
user_11622330

I think the best algorithm run O(|V| * |E|).

Algorithm:

1 - Do SCC to the graph.

2 - Build reduced graph Gr.

3 - Run one dfs for each vertex v in Gr and for each visited different SCC (including the SCC of v) accumulate the amount of vertex in them (precalculated from step 1).

With this algorithm you eliminate the |V|*|V| factor from brute force O(|V| * |V| + |V| * |E|)).

This is the best and simple algorithm that I know for this problem. I have no demonstration but I'm pretty sure there's no better way.

user_49046350
Related