2
$\begingroup$

I am trying to find the set of all vertices for which there is a path from a specific vertex $v_0$ in a directed graph. I am given the set of vertices $V$ in the beginning. I am given the edges of a graph via a stream of edges - so one directed edge $(u, v)$ at a time.

Of course, I could do a breadth or depth first traversal after I get all the edges to see which vertices I can reach from $v_0$. However, can I be determining which vertices I can visit from vertex $v_0$ while I'm reading in the edges? For instance, what if I'd like to know at any moment which vertices I can reach from $v_0$?

As you might posit, I am trying to highly optimize a program.

I tried to maintain a set of vertices that each vertex in the graph could visit, but then had trouble efficiently finding the union of these sets to get the set for $v_0$.

$\endgroup$
1
$\begingroup$

If you want to know which vertices you can reach at any moment, you may use a disjoin-set data structure. After reading an edge $(u, v)$, call union(find($u$), find($v$)). If you want to get the set of vertices reachable from $v_0$, call find($v_0$).

$\endgroup$
  • 1
    $\begingroup$ This would work for undirected graphs, but how do you propose to adapt it to the directed one? (at least that's how I'm understanding the problem, since the poster mentions directed edge) $\endgroup$ – Peter Košinár Feb 24 '14 at 3:59
  • $\begingroup$ @PeterKošinár Ah, I missed that part! I'm not sure if it is possible to adapt it for directed edges $\endgroup$ – dani_s Feb 24 '14 at 4:08
  • $\begingroup$ Yeah, the graph's directed … thanks for the inspiration though! $\endgroup$ – John Hoffman Feb 24 '14 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.