I feel like the answer is no but I'm not sure. I think it's commonly accepted that DFS runs in $O(|V| + |E|)$ time. I've read a few explanations and they all make sense if the neighbour traversal for any given vertex can be done in arbitrary order.
But I've noticed a commonly suggested DFS behavior is to traverse the neighbors in alphabetical order (i.e. CLRS exercise 22.3-2), and I don't see how this can be done in $O(|V|+|E|)$ time. This became evident to me when actually trying to implement this in runnable code.
I see two ways to do it:
- I can keep the list of vertices and each vertex's adjacency list sorted as I'm constructing the graph. However this means $O(V)$ insertion time for each new vertex in the graph, which means a total of $O(|V|^2)$ insertion time over $|V|$ nodes. And $O(|E'|)$ insertion time for a new edge where $|E'|$ is the number of neighbours in a particular vertex's adjacency list, meaning $O(|E'|^2)$ time to construct the adjacency list for any given vertex.
- Construct the graph and insert the vertices and adjacency elements in arbitrary order, but then sort them before running DFS. But comparison-based sorts are $\Omega(n\log n)$ so I'd have $O(|V|\log|V|)$ sort time for the list of vertices, and $O(|E'|\log|E'|)$ for each adjacency list.
In either case it doesn't seem like the runtime is $O(|V| + |E|)$ any more. Can someone confirm or refute? Thanks.