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

Методы дискретной оптимизацииАлгоритмы поиска в глубину и поиска вширину и их сложность1 / 20ВведениеПоиск в графе сводится к обходу вершин графа в той или инойпоследовательности. В зависимости от цели поиска, структуры графаалгоритмы обхода могут быть различными. Например, поиск данных попользователям социальной сети предполагает различные алгоритмычтения при поиске конкретного пользователя или при наборе статистикипо предпочтениям конкретных групп.

Само по себе чтение данных можетзанимать недопустимо большое время, поэтому исследованиеэффективности алгоритмов чтения является актуальной проблемой.2 / 20Представление графовДва стандартных способа хранения графов: в виде матрицы смежности ив виде списка смежности. Матрицы смежности имеют простую структуру,полезны при изучении свойств графов. При выполнении некоторыхстандартных операций, например, при определении существования ребра,соединяющего две заданные вершины, хранение графа в виде матрицысмежности позволяет выполнить эти операции наиболее быстро.Недостаток матриц смежности: необходимость хранить массивы,состоящие в основном из нулей (при малом количестве ребер графа).

Сточки зрения экономии объема памяти представление в виде матрицысмежности целесообразно в случае плотного графа, т.е. при условии, чтоотношение близко |E|/|V |2 к 1. Другой метод хранения графа –представления его в виде списка смежности. Список смежности графа G,т.е. Adj(G) – набор последовательностей вида {v|(u, v) ∈ E}∀u ∈ V . Такимобразом, список смежности состоит из |V | последовательностей, в каждойиз которой |E| элементов. Для орграфа длина списка смежности равна|E|, для неориентированного – 2|E|. В обоих случаях необходимый дляхранения объем памяти равен O(|V | + |E|). В случае матрицы смежностинеобходимый объем равен O(|V |2 ).3 / 20Обозначения1Атрибуты вершин и ребер обозначаются после точки, следующей заименем данной вершины (ребра).2Множество вершин, смежных с u, обозначается как Adj[u]. Такимобразом, списки смежности для данного графа – наборпоследовательностей Adj[u] для всех u из множества V .Задача обхода графа:Обойти все вершины графа G исходя из s ∈ V .4 / 20Поиск в ширинуСмысл термина: в данном алгоритме обход происходит в соответствии сочередностью в списке Adj[u], где в качестве начальной вершины uрассматривается s, а затем – первая в построенном списке очереди.

Длянаиболее простого описания алгоритма каждой вершине u из множестваV задаются атрибуты: цвет, расстояние от исходной вершины s, имяпредшественника, т.е. предыдущей вершины. Принцип работы алгоритмасостоит в построении очереди Q. На каждом шаге первая стоящая вочереди вершина окрашивается в красный цвет и удаляется из очереди, вкоторую по определенному правилу становятся другие вершины. Такимобразом, каждая вершина может быть окрашена в три цвета: зеленый,желтый и красный.

В красный цвет окрашивается вершина,просмотренная и удаленная из очереди. В зеленый цвет окрашенывершины, которые не поставлены в очередь. Желтые вершины – это те,которые находятся в очереди.5 / 20Поиск в ширину. Описание алгоритма1∀u ∈ V \{s} : u.color = green; u.d = ∞; u.π = ∅2s.color = yellow; s.d = 0; s.π = ∅3Q=∅4s→Q5While Q 6= ∅6Положить u: первая в списке Q7Для каждой вершины v ∈ Adj[u]8v.color = green ⇒ v.color = yellow; v.d = u.d + 1; v.π = u9v→Q10u.color = red6 / 20ПримерB=abcdefa010110b101011c010001d100000e f1 0 1 1 0 1  ; List : 0 0 0 11 0a → b, d, eb → a, c, e, fc → b, fd→ae → a, b, ff → b, c, eДля начальной вершины b последовательность шагов алгоритма:1.

Желтая вершинаu.color = yellow, v.color = green, v ∈ V \{u}, u.d = 0, Q = {b}v.d = ∞, v ∈ VAdj[u] = {a, c, e, f } ⇒a.color = yellow; a.d = 0 + 1 = 1; a.π = u = bc.color = yellow; c.d = 0 + 1 = 1; c.π = u = be.color = yellow; e.d = 0 + 1 = 1; e.π = u = bf.color = yellow; f.d = 0 + 1 = 1; f.π = u = bQ = {a, c, e, f }b.color = red7 / 20Пример2.u=aAdj[u] = {b, d, e} ⇒d.color = yellowd.d = a.d + 1 = 2d.π = aQ = {c, e, f, d}a.color = red3.u=cAdj[u] = {b, f } ⇒f.color = yellowf.d = c.d + 1 = 2f.π = cQ = {e, f, d}c.color = red8 / 20Пример4.u=eAdj[u] = {a, b, f } ⇒Q = {f, d}e.color = red5.u=fAdj[u] = {b, c, e} ⇒Q = {d}f.color = red9 / 20ПримерНа каждом шаге работы алгоритма к построенному дереву добавляетсявершина, в результате работы алгоритма строится дерево поиска:a b c d e fa → b, d a 0 1 0 1 0 0  b → a, c, e b 1 0 1 0 1 0  c→bB =  c 0 1 0 0 0 1  ; List :  d→a ; d 1 0 0 0 0 0  e→b e 0 1 0 0 0 0 f →cf 0 0 1 0 0 0a b c d e fv.d1 0 1 2 1 2 Pr ev(v) b ∅ b a b c10 / 20Анализ алгоритмаПокажем, что построенное дерево обладает свойством: для любого v ∈ Vвеличина v.d = δ(s, v), где v.d = δ(s, v) – длина кратчайшего из s в v пути.Под длиной пути из s в v понимается количество ребер при переходе.Лемма 1Для очереди Q = {vi , i = 1, 2, ..., r}, полученной на любом шаге алгоритма,справедливоvr .d ≤ v1 .d + 1,vi .d ≤ vi+1 .d, i = 1, 2, ..., r − 1Доказательство.

Пусть V = {v1 , v2 , ..., vn }. Рассуждения по индукции.Если очередь получена из вершин первого списка смежности, то послеисключения вершины v1 = s из очереди все вершины, смежные с ней,получают значение v1 .d = 1 и далее в роли вершины u выступаетследующая по списку вершина. Предположим, после изменения атрибутоввсех вершин, смежных с u, имеется очередь, первая вершина исключаетсяи рассматриваются атрибуты смежных с ней по горизонтальному списку.11 / 20Анализ алгоритмаПродолжение доказательства Леммы.

По индуктивномупредположению те вершины v1 , которые не изменили атрибуты,поскольку были в очереди ранее, удовлетворяют неравенствамu.d + 1 ≤ vi .d ≤ vi+1 .d, новые вершины, т.е. смежные с u и меняющиеатрибуты, получают значение vi .d = u.d + 1 и добавляются в конецочереди с атрибутом vi .d = u.d + 1. Это значит, что новые добавленныевершины соответствуют неравенствам леммы, что завершаетиндуктивный переход. Лемма доказана.Замечание. Если вершина vi вносится в очередь до вершины vj , тоvi .d ≤ vj .d.12 / 20Анализ алгоритмаТеорема 1Для любой начальной вершины в результате работы алгоритмасправедливо равенство v.d = δ(s, v), v ∈ V .Доказательство.

Предположим противное: для некоторой вершины vзначение атрибута d не равно кратчайшему пути от s к ней. Пустьвыбранная вершина такова, что для нее величина δ(s, v) минимальнасреди тех вершин, для которых значение d больше δ(s, v). Пусть u –вершина, непосредственно предшествующая v на кратчайшем от s до vпути, т.е.

δ(s, v) = δ(s, u) + 1. Это в частности означает, что v находится всписке смежности u. По определению v величина δ(s, u) = u.d и крометого v.d > δ(s, u) + 1 = u.d + 1. В момент удаления вершины u из очередивершина v может быть одного из трех цветов.13 / 20Анализ алгоритмаПродолжение доказательства Теоремы. Если по удалении u вершинаv зеленая, то сразу после этого полагается v.d = u.d + 1, что противоречитпредположению.

Если вершина v на момент удаления u красная, то этопротиворечит замечанию к лемме 1. Если вершина v на момент удаленияu желтая, то она приобрела такой цвет до момента удаления u, значитv.d = w.d + 1, где w – вершина, удаленная из очереди до удаления u,откуда v.d = w.d + 1 ≤ u.d + 1, что тоже невозможно. Таким образом,противоречия, полученные во всех случаях, доказывают равенствоv.d = δ(s, v), v ∈ V .

Аналогично показывается, что процедура алгоритмапроходит все вершины графа, в противном случае для некоторой вершиныv будет ∞ = v.d > δ(s, v). Теорема доказана.Замечание. Кратчайший путь из s в v, построенный алгоритмом,удовлетворяет равенству v.d = (v.π).d + 1.14 / 20Деревья поиска в ширинуВ процессе работы алгоритма строится граф предшествованияGπ = (Vπ , Eπ ), где Vπ = {v ∈ V |v.π 6= ∅} ∪ {s}, Eπ = {(v.π, v)|v ∈ V \{s}}.Теорема 2Процедура алгоритма поиска в ширину строит подграф предшествования,который является деревом поиска в ширину.Доказательство.

Необходимо показать, что для любой вершины v ∈ Vпуть из s в v является единственным простым путем. Это действительнотак, поскольку по построению графа предшествования алгоритмом поискав ширину имеется равенство |Eπ | = |Vπ | − 1 и указанный граф связен.Теорема доказана.Сложность алгоритма. При разумной организации метода времяисполнения O(n + m).15 / 20Поиск в глубинуОбщие соображения: стратегия обхода в глубину состоит в том, чтобыисследовать все ребра, выходящие из вершины, открытой последней ипроизвести возврат к вершине, когда не остается неисследованных ребер.В момент открытия вершины v, т.е.

когда ее цвет становится желтым,атрибут v.π устанавливается равным u. Подграф предшествования можетсостоять из нескольких деревьев, т.е. быть лесом. В отличие от поиска вширину у каждой вершины имеется атрибут v.f в паре с v.d. При этоматрибут v.f означает время завершения работы с v. В отличие от поиска вширину поиск в глубину работает не с очередью, а со стеком S. Пусть s –корень, т.е. начальная вершина поиска, сразу помещается в стек,полагается u = s – вершина стека. Далее возможны случаи:1Среди вершин, смежных с u, есть зеленая вершина v.

Тогда vзаписывается в стек, окрашивается в желтый цвет.2Все вершины, смежные с u, желтые. Вершина u окрашиваетсякрасным и удаляется из стека.3Стек пуст. Вершины все пройдены.16 / 20Алгоритм поиска в глубинуДля каждой вершины u ∈ V : u.color = white; u.π = ∅; time = 0. S = {s}Для каждой вершины u ∈ V :if u.color = white ⇒ time = time + 1; u.d = time; u.color = yellow.S = S ∪ {u}. Очередность перебора вершин u в соответствии со стеком S.Для каждой v ∈ Adj[u]: if v.color = white ⇒ v.pi = u; time =time + 1; v.d = time; v.color = yellow; S = S ∪ {u}.