7

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.

amit
  • 175,853
  • 27
  • 231
  • 333
Daniel
  • 30,896
  • 18
  • 85
  • 139
  • @JonathonReinhart No, algorithm questions are perfectly on topic. [example1](http://stackoverflow.com/q/14415881/572670) [example2](http://stackoverflow.com/q/22342854/572670) [example3](http://stackoverflow.com/q/3492302/572670). 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 Aug 02 '15 at 21:36
  • @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 Aug 02 '15 at 21:46
  • @JonathonReinhart There is a tag with 7k questions, [language-agnostic](http://stackoverflow.com/questions/new/language-agnostic?show=all&sort=newest), 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 Aug 02 '15 at 21:48
  • I'm sure there's a meta post where this debate rages on, but I'm unable to find it at the moment. – Jonathon Reinhart Aug 02 '15 at 21:49
  • 1
    @JonathonReinhart The canonical meta post we Programmers users like to link everyone is http://meta.programmers.stackexchange.com/questions/7182/what-goes-on-programmers-se-a-guide-for-stack-overflow Personally, my gut feeling is that this question is on topic for both SO and P.SE. – Ixrec Aug 02 '15 at 21:51
  • @Ixrec So in your opinion, would you prefer this at Programmers or SO? – Jonathon Reinhart Aug 02 '15 at 21:53
  • @JonathonReinhart If I was asking this myself, I would pick Programmers, but I don't think there's any need to migrate this off SO. – Ixrec Aug 02 '15 at 21:54
  • 2
    This question is fine on many Stack Exchange sites, **including Stack Overflow**. It should not be migrated. – durron597 Aug 02 '15 at 21:57

1 Answers1

2

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

amit
  • 175,853
  • 27
  • 231
  • 333