Лекция 3. Алгоритмы поиска в глубину и поиска в ширину и их сложность (1162199), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Если белых вершин из uне просматривается, тоS = S\{u}; u.color = red; time = time + 1; u, f = time (Завершение работыс u)Просмотр последнего элемента в списке S в качестве u. Число просмотровзеленых вершин O(E), следовательно время работы алгоритмаO(|E| + |V |).17 / 20Свойства поиска в глубинуВершина окрашивается в желтый цвет один раз, в момент включенияребра в дерево поиска.

Поскольку в случае простого связного графа числотаких окрашиваний на 1 меньше вершин, то полученный граф – дерево.Теорема 3Для любых вершин u, v графа G справедливо одно и только одно изследующих свойств:А. Отрезки [u.d, u.f ] и [v.d, v.f ] не пересекаются. u не является потомкомv в построенном лесу поиска и наоборот.Б. Отрезок [u.d, u.f ] содержится в отрезке [v.d, v.f ] и u – потомок v влесу поиска.В. Отрезок [v.d, v.f ] содержится в отрезке [u.d, u.f ] и v – потомок u влесу поиска.Доказательство. Если u.d < v.d, то вершина u была желтой в то время,когда v была зеленой.

При этом условие u.f > v.f означает, что вершина vбыла закрашена в красный и удалена из стека, т.е. v – потомок u. Случайv.f < u.d означает, что вершина v была окрашена в красный, когда uбыла еще зеленой. Следовательно, в дереве поиска эти вершины наявляются потомками друг друга. Теорема доказана.18 / 20ПримерРассмотрим предыдущий пример.1S = {b}, b.d = 1, b – желтая все другие вершины зеленые.2S = {b, a}, a.d = 2.3S = {b, a, d}, d.d = 3.4S = {b, a}, d.color = red, d.f = 4.5S = {b, a, e}, e.d = 5.6S = {b, a, e, f }, f.d = 6.7S = {b, a, e, f, c}, c.d = 7.8S = {b, a, e, f }, c.color = red, c.f = 8.9S = {b, a, e}, f.color = red, f.f = 9.10S = {b, a}, e.color = red, e.f = 10.11S = {b}, a.color = red, a.f = 11.12S – пуст19 / 20ПримерДерево поиска:20 / 20ЛитератураТ.Кормен, Ч.Лейсерзон, Р.

Риверст, К. Штайн. Алгоритмы.Построение и анализ. М., ООО «И.Д.Вильямс», 2013Скиена С. Алгоритмы. Руководство по разработке. 2-е изд.Санкт-Петербург, «БХВ-Петербург», 201420 / 20.

Характеристики

Список файлов лекций