Walking a directed graph

4
votes

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.

1
algorithmgraphdirected-graph
@JonathonReinhart No, algorithm questions are perfectly on topic. example1 example2 example3. They can be translated to any language, and directly connect to software problems. The OP has also shown an effort to solve it himself. – amit
@amit I feel like there is a lot of overlap between what's considered on-topic at Stack Overflow ("a software algorithm"), Computer Science ("algorithms, models of computation"), and Programmers ("algorithm and data structure concepts"), all quoted from their "on-topic" pages. In my opinion, if you can't tag a question with either a programming language (e.g. C), or environment (e.g. POSIX), then it's better suited for on of the other sites. This question could be answered and proven without writing a single line of code ("programming"). I've retracted my vote on precedent, but I don't agree. – Jonathon Reinhart
@JonathonReinhart There is a tag with 7k questions, language-agnostic, which is considered on-topic. All the questions in my examples are not related to any specific programming language, yet are very related to programming and were really loved by the community, so I really disagree with you on this. – amit
@JonathonReinhart The canonical meta post we Programmers users like to link everyone is meta.programmers.stackexchange.com/questions/7182/… Personally, my gut feeling is that this question is on topic for both SO and P.SE. – Ixrec
This question is fine on many Stack Exchange sites, including Stack Overflow. It should not be migrated. – durron597

1 Answers

2
votes

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|)