CODEWITHSUNDEEP
algorithmgraphdirected-graph
Daniel
Daniel

Reputation: 31609

Walking a directed graph

I have a directed acyclic graph and an origin vertex v in that graph.
How can I visit all the vertices that are reachable from v, in such a way that if I visit v1 I already visited all the vertices that have and edge to v1?

Example:

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

Starting from A, C must be visited after B.
I tried just doing a BFS and checking the parents of each vertex and if they are not visited re-add it for later, but that proved too slow, and I believe can be O(v^2).

It might help to know that the graph is somewhat binary, each vertex will be pointed to by at most two vertices. In the other direction, each vertex points to a lot of vertices.

Upvotes: 7

Views: 1884

Answers (1)

amit
amit

Reputation: 178521

You might be looking for a topological sort.

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

Using a BFS, you can leave only vertices that are reachable from v, (filter the others out), and iterate them in the order of the topological sort.

This is O(|V|+|E|), which is in your case is O(|V|) (the relaxation 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|)

Upvotes: 2

Related Questions