# Traversing a Graph polynomial time

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

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