Time complexity of a special DFS

Question

its known that DFS time complexity is O(|V|+|E|) . Suppose each vertex v has a positive weight w(v). I want to change the DFS algorithm such that when we have "exertion" of which vertex we need to add to the empty stack-we will add the most weighted vertex.

exertion means- when the stack is empty and we need to choose a vertex to start\contiue with. (sorry for being unformal)

example: if we have this directed graph:

A->B->C D->E F->G->H

and w(D)>w(A)>w(F), this new DFS on the graph will traverse this order:

D E A B C F G H

what is the time complexity of the new DFS i suggested?

Answer 1

When you select the next vertex, you need to sort the outgoing edges at the current vertex. Across all the vertices you need to sort a total of |E| elements, which will add to your complexity O(|E|log|E|).

Answer 2

You just sort all vertices in the beginning, and execute dfs through that order.

So it's VlogV + E.

I don't understand why we have to sort 'outgoing edges' in the above answer.