148
правок
Изменения
→Однопроходный алгоритм
dfs(<tex>v</tex>, -1)
<br>
Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(V + E)</tex>. Внутри него совершается еще цикл, уоторый который суммарно выполняет <tex>O(E)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно Общее время работы алгоритма <tex>O(V + E) + O(E) = O(V + E)</tex>
==Литература==
* В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
