Shouldn't a breadth first search only take $O(m)$ time?

Question

We assume the following (fairly standard) implementation for BFS.

1  procedure BFS(G,start_v):
2      let Q be a queue
3      label start_v as discovered
4      Q.enqueue(start_v)
5      while Q is not empty
6          v = Q.dequeue()
7          if v is the goal:
8              return v
9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered:
11                 label w as discovered
12                 w.parent = v
13                 Q.enqueue(w) 

The standard claim for the time complexity for BFS is that it takes $O(m+n)$ time, where $m=|E|, n=|V|$. I'm going to argue that we can improve this bound to $O(m)$, at least when the graph is undirected (the result should also hold in the directed case, with small modifications to the argument below).

The reason I believe this to be the case is that a call to BFS(G, s) is essentially the same thing as a call to BFS(G', s) where $G'=(V', E')$ is the connected component of $G$ containing $s$. By "essentially the same thing", I mean that the execution of the algorithm in either case will be identical.

It follows that an upper bound for the running time of the algorithm is $O(|V'| + |E'|)$. We have that $|E'| \leq m$. Since $G'$ is connected, we also have that $|V'| \leq |E'| + 1 \leq m+1$. It follows that the running time is also bounded by $O(m+1+m) =O(m)$.

Is there anything wrong with this reasoning? If so, explain why and exhibit an instance of the above algorithm wherein the running time is demonstrably worse than $O(m)$. If not, I have to ask why the running time is most commonly given as $O(m+n)$?

Answer 1

I believe the standard claim is that running BFS to discover the whole graph is $O(n+m)$. Your procedure just discovers the component of your start vertex, and does indeed do that in $O(m)$ time (modulo some concern about exactly how it is represented, since you need to be able to look up the neighbours of any given vertex in time that doesn't depend on how many vertices there are). To make it explore the full graph, though, you'd need to check after each iteration whether there are any vertices you haven't seen, and if so do another iteration from a suitable start vertex.