Методы систематического обхода вершин графа

Методы систематического обхода вершин графа Лекция 2 Введение Важными задачами теории графов являются задачи глобального анализа как неориентированных, так и ориентированных графов. К этим задачам относятся, например, задачи поиска циклов или контуров, вычисление длин путей между парами вершин, перечисление путей с теми или иными свойствами и т.п. Глобальный анализ графа следует отличать от локального, примером которого может служить задача определения множеств предшественников и преемников фиксированной вершины ориентированного графа. Базой для решения многих задач глобального анализа являются алгоритмы обхода или поиска. Необходимо уметь обходить все вершины графа таким образом, чтобы каждая вершина была отмечена ровно один раз. Обычно такое "путешествие" по графу сопровождается нумерацией вершин графа в том порядке, в котором они отмечаются, а также определенной "маркировкой" ребер (или дуг) графа. Существуют две основные стратегии таких обходов: поиск в глубину и поиск в ширину Поиск в глубину • При поиске в глубину, отправляясь в "путешествие" по графу из некоторой начальной вершины , мы действуем следующим образом. Пусть, "путешествуя", мы достигли некоторой вершины (в начале "путешествия" ). Отмечаем вершину и просматриваем вершины из ее списка смежности . • При условии, что в этом списке существует хотя бы одна неотмеченная вершина, продолжаем "путешествие" из первой такой вершины , действуя как описано выше — "ныряем" вглубь, т.е. просматриваем вершины списка смежности вершины , откладывая анализ других элементов как возможных продолжений поиска "на потом". Если же неотмеченных вершин в нет, то возвращаемся из в ту вершину, из которой мы в нее попали, и продолжаем анализировать список смежности этой вершины. "Путешествие" прекратится в тот момент, когда мы вернемся в начальную вершину и либо все вершины будут отмеченными, либо окажется, что неотмеченные вершины есть, но из больше никуда пойти нельзя. В последнем случае возможны продолжение поиска из новой вершины или остановка, что определяется конкретной версией алгоритма. Заметим, что результат поиска в глубину зависит от порядка вершин в списках смежности, представляющих граф, а также от выбора начальной вершины Поиск в глубину (Depth-first search, DFS) Пусть задан граф G = (V, E). Алгоритм поиска описывается следующим образом: для каждой новой вершины необходимо найти все новые смежные вершины и повторить поиск для них. Пусть в начальный момент времени все вершины отмечены как непросмотренные(новые) 1) Из множества всех непросмотренных вершин выберем любую вершину: v1. 2) Выполним для нее процедуру DFS(v1). 3) Отметим ее как просмотренную Повторяем шаги 1-3 до тех пор, пока множество просмотренных вершин не пусто. Алгоритм поиска в глубину • • • • • Шаг 1. Всем вершинам графа присваивается значение «новая». Выбирается первая вершина и помечается как посещенная. Шаг 2. Для последней помеченной как посещенная вершины выбирается первая смежная новая вершина, и ей присваивается значение посещенная. Если таких вершин нет, то берется предыдущая помеченная вершина. Шаг 3. Повторить шаг 2 до тех пор, пока все вершины не будут помечены как посещенные. Также часто используется нерекурсивный алгоритм поиска в глубину. В этом случае рекурсия заменяется на стек. Как только вершина просмотрена, она помещается в стек, а использованной она становится, когда больше нет новых вершин, смежных с ней. Временная сложность зависит от представления графа. Если применена матрица смежности, то временная сложность равна O(n2), а если нематричное представление – O(n+m): рассматриваются все вершины и все ребра. Обход в глубину Метод поиска в глубину Данные: G = (V, E) –граф, заданный списками смежности Можно описать процедуру рекурсивного поиска в глубину на условном алгоритмическом языке: procedure ПОИСК В ГЛУБИНУ В ГРАФЕ G(v) {поиск в глубину из вершины v; переменные НОВЫЙ, ЗАПИСЬ – глобальные} begin рассмотреть v; НОВЫЙ[v] := ложь; for u ∈ ЗАПИСЬ[v] do if НОВЫЙ[u] then ПОИСК В ГЛУБИНУ В ГРАФЕ G(u) end. {вершина v использована} Представим фрагмент программы, соответствующий вышеописанной процедуре: • • • • • • • • • • • • • • • • • • procedure Depth_First_Search(v : Integer); var u : Integer; p : PT; begin Nov[v] := False; p := Start[v]; write(v,' '); while p <> nil do begin u := p^.Uzl; if Nov[u] then begin Depth_First_Search(u); end; p := p^.Next; end; end; Анализ вычислительной сложности алгоритма Алгоритм просматривает каждое ребро один раз, и выполняет для каждой вершины константное число действий. Обозначая число вершин как V, а ребер — как E, получаем, что время работы — O(V+E). Глубина рекурсии, в которой мы находимся, не превышает общего числа вызовов функции DFS — числа вершин. То есть, объем памяти, необходимый для работы алгоритма, равен O(V). Общее число операций: O(|V|+|E|) Свойства поиска в глубину Времена обнаружения и окончания обработки вершин образуют правильную скобочную структуру. S 1 2 3 4 5 6 7 8 9 10 (s(z(y(xx)y)(ww)z)s) Z y x w Стек ( Last-In-First-Out ) • • Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции: pushДобавить (положить) в конец стека новый элемент popИзвлечь из стека последний элемент backУзнать значение последнего элемента (не удаляя его) sizeУзнать количество элементов в стеке clearОчистить стек (удалить из него все элементы) Зачем все это нужно? Наверное, ни одна структура данных не применяется в компьютерной индустрии так широко, как стек. Операционные системы построены на этой простой структуре данных, и наверное каждый программист неоднократно получал радостное сообщение о переполнении стека в .своей программе. • Стек - это структура данных присущая всей программируемой технике. Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Часто стек называют магазином — по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним). • При вызове функции в стек копируется адрес для возврата после окончания выполнения данной подпрограммы. По окончании её выполнения адрес возвращается из стека в счетчик команд и программа продолжает выполняться с места после функции. Также в стек необходимо помещать регистры, которые используются в данной подпрограмме (в языках высокого уровня этим занимается компилятор). Все вышесказанное характерно для так называемого аппаратного стека. • такая структура данных (LIFO - last in, first out) полезна далеко не только при работе на низком уровне. Часто возникает необходимость хранить данные в таком порядке (например известный алгоритм разбора арифметических выражений основан на работе со стеком), тогда программисты реализуют программный стек. Пример реализации структуры стэк Хранить элементы стека мы будем в массиве. Для начала будем считать, что максимальное количество элементов в стеке не может превосходить константы MAX_SIZE, тогда для хранения элементов массива необходимо создать массив размера MAX_SIZE. • Объявим структуру данных типа stack. const int MAX_SIZE=1000; struct stack { int m_size; // Количество элементов в стеке int m_elems[MAX_SIZE]; // Массив для хранения элементов stack(); // Конструктор ~stack(); // Деструктор void push(int d); // Добавить в стек новый элемент int pop(); // Удалить из стека последний элемент // и вернуть его значение int back(); // Вернуть значение последнего элемента int size(); // Вернуть количество элементов в стеке void clear(); // Очистить стек }; Объявленная здесь структура данных stack реализует стек целых чисел. Поле структуры m_size хранит количество элементов в стеке в настоящее время, сами Очередь • ( First-in-Firsf –Out ) Очередью (aнгл. queue)) называется структура данных, в которой элементы добавляют в конец, а извлекают из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других. Описание структуры очередь: const int MAX_SIZE=1000; struct queue { int m_size; // Количество элементов в очереди int m_start; // Номер элемента, с которого начинается очередь int m_elems[MAX_SIZE]; // Массив для хранения элементов queue(); // Конструктор ~queue(); // Деструктор void push(int d); // Добавить в очередь новый элемент int pop(); // Удалить из очереди первый элемент // и вернуть его значение int front(); // Вернуть значение первого элемента int size(); // Вернуть количество элементов в очереди void clear(); // Очистить очередь }; Нерекурсивный вариант • Поскольку на основе алгоритмов обхода графов поиском в глубину решается большой круг типовых задач (построение каркаса, нахождение компонент двусвязности графа, и т.д.), приведем также нерекурсивный вариант реализации алгоритма обхода графа поиском в глубину: Использование стека для обхода графа Граф: Если в качестве промежуточной структуры хранения при обходе использовать стек, то получим обход в глубину. 2 1 3 1 5 8 7 6 4 3 2 4 6 5 Можно также получить дерево обхода в глубину, если отмечать каждую прямую или обратную дугу. 7 1 8 Стек: 1 2 4 3 7 6 5 8 2 3 4 5 6 7 8 4 1 3 4 1 6 1 7 5 5 • procedure Depth_First_Search1(v : Integer); • begin • СТЕК:=NIL; • СТЕК<=v; { вершина v помещается в СТЕК} • Рассмотреть v; • Новый [v] := ложь; • while СТЕК do • begin • verh:=top(СТЕК); • {переходим в первую из списка соседку вершины verh} • If НАЧАЛО[verh]=NIL then b:=ложь; • Else b:=notНОВЫЙ[НАЧАЛО[verh]^.uzl]; • While b do • • • • • • • • • • • • • • • • • • • Begin НАЧАЛО[verh]:= НАЧАЛО[verh]^.next; {переход на следующую запись в списке ЗАПИСЬ[verh]} If НАЧАЛО[verh]=NIL then b:=ложь; Else b:=notНОВЫЙ[НАЧАЛО[verh]^.uzl]; {проверка, будет ли следующая соседка новой} end; if НАЧАЛО[verh]=nil then {найдена новая вершина} begin verh:=НАЧАЛО[verh]^.uzl; СТЕК<=verh; {помещаем новую вершину в СТЕК} Рассмотреть verh; НОВЫЙ[verh]:=ложь; End; Else {вершина verh уже использована, удаляем ее из СТЕКА} Verh<=СТЕК; End {while СТЕК} End; { Depth_First_Search1} Зачем это надо? • На больших графах поиск в глубину серьёзно нагружает стек вызовов. • Если есть риск переполнения стека, используют нерекурсивные варианты поиска. Применение алгоритма поиска в глубину • • • • Поиск в глубину — хороший инструмент для исследования топологических свойств графов. Например: В качестве подпрограммы в алгоритмах поиска однои двусвязных компонент. В топологической сортировке. В различных расчётах на графах. Например, как часть алгоритма Диница поиска максимального потока. Поиск в глубину — естественный выбор для решения задач о лабиринте. АЛГОРИТМ ОБХОДА ГРАФА НА ОСНОВЕ ПОИСКА В ШИРИНУ • При поиске в ширину (breadth-first search), после посещения первой вершины, посещаются все соседние с ней вершины. Потом посещаются все вершины, находящиеся на расстоянии двух ребер от начальной. При каждом новом шаге посещаются вершины, расстояние от которых до начальной на единицу больше предыдущего. Чтобы предотвратить повторное посещение вершин, необходимо вести список посещенных вершин. Для хранения временных данных, необходимых для работы алгоритма, используется очередь – упорядоченная последовательность элементов, в которой новые элементы добавляются в конец, а старые удаляются из начала. • Таким образом, основная идея поиска в ширину заключается в том, что сначала исследуются все вершины, смежные с начальной вершиной (вершина с которой начинается обход). Эти вершины находятся на расстоянии 1 от начальной. Затем исследуются все вершины на расстоянии 2 от начальной, затем все на расстоянии 3 и т.д. Обратим внимание, что при этом для каждой вершины сразу находятся длина кратчайшего маршрута от начальной вершины. • В результате поиска в ширину находится путь кратчайшей длины в невзвешенном графе, т.е. путь, содержащий наименьшее число рёбер. Обход в ширину Вычислительная сложность • Сложность поиска в ширину при нематричном представлении графа равна O(n+m), ибо рассматриваются все n вершин и m ребер. Использование матрицы смежности приводит к оценке O(n2) Алгоритм поиска в ширину • Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная (и заносится в очередь). • Шаг 2. Посещается первая вершина из очереди (если она не помечена как посещенная). Все ее соседние вершины заносятся в очередь. После этого она удаляется из очереди. • Шаг 3. Повторяется шаг 2 до тех пор, пока очередь не пуста. • Ниже приведена запись процедуры поиска в ширину на условном алгоритмическом языке. • • • • • • • • • • • • • • • • • • Procedure ПОИCК В ШИРИНУ В ГРАФЕ (v1,v2) begin ОЧЕРЕДЬ:=NIL; ОЧЕРЕДЬ<=v;{вершина v помещается в очередь} НОВЫЙ[v]:=ложь; While ОЧЕРЕДЬ do Begin Niz<=ОЧЕРЕДЬ; {выталкивание из очереди нижнего элемента} For u € ЗАПИСЬ[niz] do {поиск всех новых соседок вершины niz} If НОВЫЙ[u] then Begin ОЧЕРЕДЬ<=u; НОВЫЙ[u]:=ложь; End End {while ОЧЕРЕДЬ} end; // ПОИCК В ШИРИНУ В ГРАФЕ Использование очереди Граф: В качестве промежуточной структуры хранения при обходе в ширину будем использовать очередь. 2 1 3 1 2 4 5 3 6 7 8 4 6 5 7 8 Можно также получить дерево обхода в ширину, если отмечать каждую прямую дугу. 1 Очередь: 1 2 4 3 7 6 5 8 2 3 4 5 6 7 8 1 2 1 1 4 5 5 • вызов процедуры ПОИCК В ШИРИНУ В ГРАФЕ G(v) приводит к посещению всех вершин связной компоненты графа, содержащей вершину v, причем каждая вершина просматривается в точности один раз. • Вычислительная сложность алгоритма поиска в ширину также имеет порядок O(m + n), так как каждая вершина (всего n вершин) помещается в очередь и удаляется из очереди в точности один раз, а число итераций цикла «For u € ЗАПИСЬ[niz]», очевидно, будет иметь порядок числа ребер (всего m ребер) графа. История и сферы применения алгоритма • • Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте. Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах. Применение: • • • • • • • • Волновой алгоритм поиска пути в лабиринте Волновая трассировка печатных плат Поиск компонент связности в графе Поиск кратчайшего пути между двумя узлами невзвешенного графа Поиск в пространстве состояний: нахождение решения задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа Нахождение кратчайшего цикла в ориентированном невзвешенном графе Нахождение всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами Поиск увеличивающего пути в алгоритме Форда-Фалкерсона (алгоритм Эдмондса-Карпа) Нахождение кратчайшего пути в лабиринте 4 5 14 4 3 2 13 5 3 12 6 6 4 11 7 7 5 10 6 11 1 1 2 15 7 13 8 14 9 15 10 12 16 3 9 6 2 2 7 8 9 10 1 2 3 4 2 8 13 14 15 2 20 8 19 9 16 17 18 17 19 20 17 18 19 18 19 20 19 5 1. Пометить числом 1 и поместить входную клетку в очередь. 2. Взять из очереди клетку. Если это выходная клетка, то перейти на шаг 4, иначе пометить все непомеченные соседние клетки числом , на 1 большим, чем данная, и поместить их в очередь. 3. Если очередь пуста, то выдать «Выхода нет» и выйти, иначе перейти на шаг 2. 4. Обратный ход: начиная с выходной клетки, каждый раз смещаться на клетку, помеченную на 1 меньше, чем текущая, пока не дойдем до входной клетки. При проходе выделять пройденные клетки.