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|)
.
Time complexity of a special DFS
-
31-08-2022 - |
Pergunta
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?
Solução
Outras dicas
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.