Сложность времени специального DFS

Question

известно, что сложность времени DFS равна O(|V|+|E|). Предположим, что каждая вершина v имеет положительный вес w(v). Я хочу изменить алгоритм DFS таким образом, что, когда у нас есть «напряжение», из которой мы должны добавить в пустой стек, мы добавим самую взвешенную вершину.

Напряжение означает, когда стек пуст, и нам нужно выбрать вершину, чтобы начать \ contiue с. (Извините за неформальным)

примера: если мы имеем этот ориентированный граф:

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

и w(D)>w(A)>w(F), этот новый ДФС на графике будет проходить этот заказ:

D E A B C F G H 

что временная сложность новой DFS я предложил?

Answer 1

Когда вы выбираете следующую вершину, вам нужно отсортировать исходящие ребра в текущей вершине. Через все вершины вам нужно отсортировать в целом |E| элементов, которые добавят к вашей сложности O(|E|log|E|).

Answer 2

Вы просто сортируете все вершины в начале и выполняете dfs через этот порядок.

Так что VlogV + E.

Я не понимаю, почему мы должны сортировать «исходящие ребра» в ответе выше.