- Slicing 100GB raster datasets
- How to properly display the Copyright information in the User Interface or product documentation?
- If I become sick with a fever in the restaurant I work in and they refuse to let me leave
- How to argue a biaised District Judge Order of Possession in Permission to appeal in UK
- Cause of random hangs
- Read the first line of the current file to process it in a command (Emulating %TeX root)
- Toggle explorer window
- Have a car draw random circles in a cartesian plane
- How to write the Rotation matrix kinematic equation for the desired motion?
- What is the most common control method in Underfloor heating?
- computational assistance
- Is a universal basic income as the only means of monetary creation compatible with the global economy?
- Relationship between private transactions and central banks' interventions
- Where relative wages settle in the Ricardian model
- Disable autoalignment on equals
- Freeform plugin unique submission amount
- An Arranged Riley Riddle
- Megan mated by a king move
- How to statistically prove that a column in a dataframe is not needed
- How to add values to new row to a csv in python
Can Depth-first search (DFS) with alphabetical traversal of neighbors be run in O(|V|+|E|) time?
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