First, how to store a graph. There are two ways and they are not equivalent.

An adjacency list

For each node, a list of its neighbours:

adj[0] = [1, 47]
adj[1] = [0, 2]
adj[2] = [1]
...

Memory: O(V + E). Visiting the neighbours: as many steps as there are neighbours.

An adjacency matrix

One bit for every pair of nodes, edge or no edge:

     0  1  2  3
  0  .  1  .  .
  1  1  .  1  .
  2  .  1  .  .
  3  .  .  .  .

Memory: O(V²). The question "is there an edge A–B?" takes one step, with no searching. But visiting the neighbours takes V steps, even when there are none.

In lesson 2 you worked out what slice headers would cost transit. That was an argument, not a measurement, and that lesson's gotcha said so plainly. Step 7 of this lesson measures the same question.

BFS — breadth-first

BFS(from, to):
    prev[*] ← −1;  seen[from] ← true
    queue ← [from]
    while queue is not empty:
        v ← FRONT of queue           // ← a queue
        if v = to: return the path
        for each neighbour w:
            c.Hit()
            if seen[w]: skip
            seen[w] ← true; prev[w] ← v
            queue ← queue + w

A queue visits nodes in layers: first everything one hop away, then everything two hops away, and so on. So the first time to is reached, it must be by the shortest path in hops — there is no shorter layer left.

DFS — depth-first

DFS(from, to):
    prev[*] ← −1
    stack ← [from]
    while stack is not empty:
        v ← BACK of stack            // ← a stack; the ONLY difference
        if seen[v]: skip
        seen[v] ← true
        if v = to: return the path
        for each neighbour w:
            c.Hit()
            if seen[w]: skip
            prev[w] ← v; stack ← stack + w

Compare the two. One line differs — FRONT of queue against BACK of stack — plus one detail: DFS checks seen when it takes, not when it puts, because the same node can be pushed several times before its turn comes.

A stack goes as deep as it can, hits a dead end, and backs up. There are no layers, so there is no promise about length.

And a third version

DFSRecursive(v):
    seen[v] ← true
    if v = to: found
    for each neighbour w:
        if not seen[w]: prev[w] ← v; DFSRecursive(w)

There is no stack here — because there is one: the call stack. Lesson 5 already showed and measured that; step 6 shows where the equivalence has a limit.

The cost

Both searches visit every node at most once and every edge at most twice — once from each end. So:

O(V + E) — for both.

The complexity is the same. What differs is not the cost but the answer.