Latest update

# Can Depth-first search (DFS) with alphabetical traversal of neighbors be run in O(|V|+|E|) time?

2018-07-19 18:38:55

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