Oriented graph walk

Question

I have a directed acyclic graph and a vertex beginning v in this graph.
How can I visit all the vertices reachable from v , so that if I am in v1 , I have already visited all the vertices that have an edge up to v1 ?

Example:

 /-----V A->B->C 

Starting from A , C must be visited after B
I tried just doing BFS and checking the parents of each vertex, and if they are not visited, re-add them later, but this turned out to be too slow, and I think it could be O(v^2) .

This can help to find out that the graph is somewhat binary, each vertex will be indicated by no more than two vertices. In the other direction, each vertex points to many vertices.

Answer 1

You may be looking for topological sorting .

First we do a topological sorting and get the order of the vertices in the graph according to this type, let it be v1,v2,...,vn .

Using BFS, you can leave only the vertices reachable from v (filter the rest) and repeat them in topological sort order.

This is O(|V|+|E|) , which in your case is O(|V|) (relaxation of each vertex will be pointed to by at most two vertices suggests |E| <= 2|V| , and thus , O(|V|+|E|) <= O|V|+2|V|) = O(3|V|) = O(|V|)