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.
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|)
下一篇: 走有向图