Изменения

Перейти к: навигация, поиск

Обход в глубину, цвета вершин

13 байт добавлено, 01:39, 25 октября 2011
Время работы
=== Время работы ===
Оценим время работы обхода в глубину. Процедура <tex>dfs</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие ребра <tex>\{e\ |\ begin(e) = u\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.
== Цвета вершин ==
Анонимный участник

Навигация