Given a directed graph $G = (V, E)$ and a starting vertex $v_1$.

The graphs edges is this

$\{(v_1, v_2), (v_2, v_3), (v_3, v_4)\}$

basically below

$(v_1) \to (v_2) \to (v_3) \to (v_4)$

Can we traverse this graph and record the path starting at $v_1$ in $O(|V|)$ time?

For example Making a list like $[(v_1, v_2), (v_2, v_3), (v_3, v_4)]$

I'm confused whether this takes $O(|V|^2)$ worst case time because the edges are in a set

  • $\begingroup$ How is the graph given to you? Also, in order to consider asymptotics, you should define a general problem. $\endgroup$ – Yuval Filmus Jul 22 at 2:17
  • $\begingroup$ $(v_1) \to (v_2) \to \dots \to (v_n)$. No other edges and we are given only the starting $(v_1)$. $\endgroup$ – Tree Garen Jul 22 at 2:23
  • $\begingroup$ Are the edges ordered? $\endgroup$ – Yuval Filmus Jul 22 at 2:23
  • $\begingroup$ Yes from $v_1$ to $v_n$ $\endgroup$ – Tree Garen Jul 22 at 2:24
  • 1
    $\begingroup$ They’re the same in your case. $\endgroup$ – Yuval Filmus Jul 22 at 2:25

Your Answer

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

Browse other questions tagged or ask your own question.