Обход графа в ширину

добавлено: 10 Jun 2008 19:30
редактировано: 10 Dec 2012 16:05

Содержание [скрыть][показать]

Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры

Постановка задачи

Дан ориентированный или неориентированный взвешенный граф с вершинами и рёбрами. Веса всех рёбер неотрицательны. Указана некоторая стартовая вершина . Требуется найти длины кратчайших путей из вершины во все остальные вершины, а также предоставить способ вывода самих кратчайших путей.

Эта задача называется «задачей о кратчайших путях с единственным источником» (single-source shortest paths problem).

Алгоритм

Здесь описывается алгоритм, который предложил голландский исследователь Дейкстра (Dijkstra) в 1959 г.

Заведём массив , в котором для каждой вершины будем хранить текущую длину кратчайшего пути из в . Изначально , а для всех остальных вершин эта длина равна бесконечности (при реализации на компьютере обычно в качестве бесконечности выбирают просто достаточно большое число, заведомо большее возможной длины пути):

Кроме того, для каждой вершины будем хранить, помечена она ещё или нет, т.е. заведём булевский массив . Изначально все вершины не помечены, т.е.

Сам алгоритм Дейкстры состоит из итераций.

На очередной итерации выбирается вершина с наименьшей величиной среди ещё не помеченных, т.е.:

(Понятно, что на первой итерации выбрана будет стартовая вершина .)

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

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

Стоит заметить, что, если не все вершины графа достижимы из вершины , то значения для них так и останутся бесконечными. Понятно, что несколько последних итераций алгоритма будут как раз выбирать эти вершины, но никакой полезной работы производить эти итерации не будут (поскольку бесконечное расстояние не сможет прорелаксировать другие, даже тоже бесконечные расстояния). Поэтому алгоритм можно сразу останавливать, как только в качестве выбранной вершины берётся вершина с бесконечным расстоянием.

Восстановление путей. Разумеется, обычно нужно знать не только длины кратчайших путей, но и получить сами пути. Покажем, как сохранить информацию, достаточную для последующего восстановления кратчайшего пути из до любой вершины. Для этого достаточно так называемого массива предков: массива , в котором для каждой вершины хранится номер вершины , являющейся предпоследней в кратчайшем пути до вершины . Здесь используется тот факт, что если мы возьмём кратчайший путь до какой-то вершины , а затем удалим из этого пути последнюю вершину, то получится путь, оканчивающийся некоторой вершиной , и этот путь будет кратчайшим для вершины . Итак, если мы будем обладать этим массивом предков, то кратчайший путь можно будет восстановить по нему, просто каждый раз беря предка от текущей вершины, пока мы не придём в стартовую вершину — так мы получим искомый кратчайший путь, но записанный в обратном порядке. Итак, кратчайший путь до вершины равен:

Осталось понять, как строить этот массив предков. Однако это делается очень просто: при каждой успешной релаксации, т.е. когда из выбранной вершины происходит улучшение расстояния до некоторой вершины , мы записываем, что предком вершины является вершина :

Доказательство

Основное утверждение, на котором основана корректность алгоритма Дейкстры, следующее. Утверждается, что после того как какая-либо вершина становится помеченной, текущее расстояние до неё уже является кратчайшим, и, соответственно, больше меняться не будет.

Доказательство будем производить по индукции. Для первой итерации справедливость его очевидна — для вершины имеем , что и является длиной кратчайшего пути до неё. Пусть теперь это утверждение выполнено для всех предыдущих итераций, т.е. всех уже помеченных вершин; докажем, что оно не нарушается после выполнения текущей итерации. Пусть — вершина, выбранная на текущей итерации, т.е. вершина, которую алгоритм собирается пометить. Докажем, что действительно равно длине кратчайшего пути до неё (обозначим эту длину через ).

Рассмотрим кратчайший путь до вершины . Понятно, этот путь можно разбить на два пути: , состоящий только из помеченных вершин (как минимум стартовая вершина будет в этом пути), и остальная часть пути (она тоже может включать помеченные вершины, но начинается обязательно с непомеченной). Обозначим через первую вершину пути , а через — последнюю вершины пути .

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

Вследствие неотрицательности стоимостей рёбер длина кратчайшего пути (а она по только что доказанному равна ) не превосходит длины кратчайшего пути до вершины . Учитывая, что (ведь алгоритм Дейкстры не мог найти более короткого пути, чем это вообще возможно), в итоге получаем соотношения:

С другой стороны, поскольку и , и — вершины непомеченные, то так как на текущей итерации была выбрана именно вершина , а не вершина , то получаем другое неравенство:

Из этих двух неравенств заключаем равенство , а тогда из найденных до этого соотношений получаем и:

что и требовалось доказать.

Реализация

Итак, алгоритм Дейкстры представляет собой итераций, на каждой из которых выбирается непомеченная вершина с наименьшей величиной , эта вершина помечается, и затем просматриваются все рёбра, исходящие из данной вершины, и вдоль каждого ребра делается попытка улучшить значение на другом конце ребра.

Время работы алгоритма складывается из:

При простейшей реализации этих операций на поиск вершины будет затрачиваться операций, а на одну релаксацию — операций, и итоговая асимптотика алгоритма составляет:

Реализация:

constint INF =1000000000;   int main(){int n; …

чтение n … vector< vector < pair<int,int>>> g (n); … чтение графа … int s = …;// стартовая вершина   vector<int> d (n, INF), p (n); d[s]=0; vector<char> u (n);for(int i=0; i<n;++i){int v =-1;for(int j=0; j<n;++j)if(!u[j]&&(v ==-1|| d[j]< d[v])) v = j;if(d[v]== INF)break; u[v]=true;   for(size_t j=0; j<g[v].size();++j){int to = g[v][j].first, len = g[v][j].second;if(d[v]+ len < d[to]){ d[to]= d[v]+ len; p[to]= v;}}}}

Здесь граф хранится в виде списков смежности: для каждой вершины список содержит список рёбер, исходящих из этой вершины, т.е. список пар , где первый элемент пары — вершина, в которую ведёт ребро, а второй элемент — вес ребра.

После чтения заводятся массивы расстояний , меток и предков . Затем выполняются итераций. На каждой итерации сначала находится вершина , имеющая наименьшее расстояние среди непомеченных вершин. Если расстояние до выбранной вершины оказывается равным бесконечности, то алгоритм останавливается. Иначе вершина помечается как помеченная, и просматриваются все рёбра, исходящие из данной вершины, и вдоль каждого ребра выполняются релаксации. Если релаксация успешна (т.е. расстояние меняется), то пересчитывается расстояние и сохраняется предок .

После выполнения всех итераций в массиве оказываются длины кратчайших путей до всех вершин, а в массиве — предки всех вершин (кроме стартовой ). Восстановить путь до любой вершины можно следующим образом:

vector<int> path;for(int v=t; v!=s; v=p[v]) path.push_back(v); path.push_back(s); reverse (path.begin(), path.end());

Литература

 

 

 

 


добавлено: 10 Jun 2008 19:17
редактировано: 25 May 2012 14:18

Содержание [скрыть][показать]

Поиск в ширину

Поиск в ширину (обход в ширину, breadth-first search) — это один из основных алгоритмов на графах.

В результате поиска в ширину находится путь кратчайшей длины в невзвешенном графе, т.е. путь, содержащий наименьшее число рёбер.

Алгоритм работает за , где — число вершин, — число рёбер.

Описание алгоритма

На вход алгоритма подаётся заданный граф (невзвешенный), и номер стартовой вершины .

Граф может быть как ориентированным, так и неориентированным, для алгоритма это не важно.

Сам алгоритм можно понимать как процесс «поджигания» графа: на нулевом шаге поджигаем только вершину . На каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей; т.е.

за одну итерацию алгоритма происходит расширение «кольца огня» в ширину на единицу (отсюда и название алгоритма).

Более строго это можно представить следующим образом. Создадим очередь , в которую будут помещаться горящие вершины, а также заведём булевский массив , в котором для каждой вершины будем отмечать, горит она уже или нет (или иными словами, была ли она посещена).

Изначально в очередь помещается только вершина , и , а для всех остальных вершин . Затем алгоритм представляет собой цикл: пока очередь не пуста, достать из её головы одну вершину, просмотреть все рёбра, исходящие из этой вершины, и если какие-то из просмотренных вершин ещё не горят, то поджечь их и поместить в конец очереди.

В итоге, когда очередь опустеет, обход в ширину обойдёт все достижимые из вершины, причём до каждой дойдёт кратчайшим путём. Также можно посчитать длины кратчайших путей (для чего просто надо завести массив длин путей ), и компактно сохранить информацию, достаточную для восстановления всех этих кратчайших путей (для этого надо завести массив «предков» , в котором для каждой вершины хранить номер вершины, по которой мы попали в эту вершину).

Реализация

Реализуем вышеописанный алгоритм на языке C++.

Входные данные:

  vector < vector<int>> g;// графint n;// число вершинint s;// стартовая вершина (вершины везде нумеруются с нуля)   // чтение графа …

Сам обход:

  queue<int> q; q.push(s); vector<bool> used (n); vector<int> d (n), p (n); used[s]=true; p[s]=-1;while(!q.empty()){int v = q.front(); q.pop();for(size_t i=0; i<g[v].size();++i){int to = g[v][i];if(!used[to]){ used[to]=true; q.push(to); d[to]= d[v]+1; p[to]= v;}}}

Если теперь надо восстановить и вывести кратчайший путь до какой-то вершины , это можно сделать следующим образом:

  if(!used[to])cout<<"No path!";else{ vector<int> path;for(int v=to; v!=-1; v=p[v]) path.push_back(v); reverse (path.begin(), path.end());cout<<"Path: ";for(size_t i=0; i<path.size();++i)cout<< path[i]+1<<" ";}

Приложения алгоритма

  • Поиск кратчайшего пути в невзвешенном графе.
  • Поиск компонент связности в графе за .

    Для этого мы просто запускаем обход в ширину от каждой вершины, за исключением вершин, оставшихся посещёнными () после предыдущих запусков. Таким образом, мы выполняем обычный запуск в ширину от каждой вершины, но не обнуляем каждый раз массив , за счёт чего мы каждый раз будем обходить новую компоненту связности, а суммарное время работы алгоритма составит по-прежнему (такие несколько запусков обхода на графе без обнуления массива называются серией обходов в ширину).

  • Нахождения решения какой-либо задачи (игры) с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа.

    Классический пример — игра, где робот двигается по полю, при этом он может передвигать ящики, находящиеся на этом же поле, и требуется за наименьшее число ходов передвинуть ящики в требуемые позиции. Решается это обходом в ширину по графу, где состоянием (вершиной) является набор координат: координаты робота, и координаты всех коробок.

  • Нахождение кратчайшего пути в 0-1-графе (т.е. графе взвешенном, но с весами равными только 0 либо 1): достаточно немного модифицировать поиск в ширину: если текущее ребро нулевого веса, и происходит улучшение расстояния до какой-то вершины, то эту вершину добавляем не в конец, а в начало очереди.
  • Нахождение кратчайшего цикла в ориентированном невзвешенном графе: производим поиск в ширину из каждой вершины; как только в процессе обхода мы пытаемся пойти из текущей вершины по какому-то ребру в уже посещённую вершину, то это означает, что мы нашли кратчайший цикл, и останавливаем обход в ширину; среди всех таких найденных циклов (по одному от каждого запуска обхода) выбираем кратчайший.
  • Найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин . Для этого надо запустить 2 поиска в ширину: из , и из . Обозначим через массив кратчайших расстояний, полученный в результате первого обхода, а через — в результате второго обхода. Теперь для любого ребра легко проверить, лежит ли он на каком-либо кратчайшем пути: критерием будет условие .
  • Найти все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин . Для этого надо запустить 2 поиска в ширину: из , и из . Обозначим через массив кратчайших расстояний, полученный в результате первого обхода, а через — в результате второго обхода. Теперь для любой вершины легко проверить, лежит ли он на каком-либо кратчайшем пути: критерием будет условие .
  • Найти кратчайший чётный путь в графе (т.е. путь чётной длины). Для этого надо построить вспомогательный граф, вершинами которого будут состояния , где — номер текущей вершины, — текущая чётность. Любое ребро исходного графа в этом новом графе превратится в два ребра и . После этого на этом графе надо обходом в ширину найти кратчайший путь из стартовой вершины в конечную, с чётностью, равной 0.

Задачи в online judges

Список задач, которые можно сдать, используя обход в ширину:

 

 

 

 


Существует достаточно много алгоритмов работы с древовидными структурами, в которых часто встречается понятие обхода (traversing) дерева или «прохода» по дереву. При таком методе исследования дерева каждый узел посещается только один раз, а полный обход задает линейное упорядочивание узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие «следующий» узел. т.е. узел стоящий после данного при выбранном порядке обхода.

Существует несколько принципиально разных способов обхода дерева:

Каждый узел посещается до того, как посещены его потомки.

Для корня дерева рекурсивно вызывается следующая процедура:

Посетить узел Обойти левое поддерево Обойти правое поддерево

Примеры использования обхода:

  • решение задачи методом деления на части
  • разузлование сверху
  • стратегия «разделяй и властвуй» (Сортировка Фон Hеймана, быстрая сортировка, одновременное нахождение максимума и минимума последовательности чисел, умножение длинных чисел).

Посещаем сначало левое поддерево, затем узел, затем — правое поддерево.

Для корня дерева рекурсивно вызывается следующая процедура:

Обойти левое поддерево Посетить узел Обойти правое поддерево

Узлы посещаются ‘снизу вверх’.

Для корня дерева рекурсивно вызывается следующая процедура:

Обойти левое поддерево Обойти правое поддерево Посетить узел

Примеры использования обхода:

  • анализ игр с полной информацией
  • разузлование снизу
  • динамическое программирование

При обходе в ширину узлы посещаются уровень за уровнем(N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.

Для реализации используется структура queue — очередь с методами

  • enqueue — поставить в очередь
  • dequeue — взять из очереди
  • empty — возвращает TRUE, если очередь пуста, иначе — FALSE

q.enqueue(root); // корень в очередь while (! q.empty) { x = q.dequeue(); visit x; // посетить x if (! x.left.empty) // x.left — левое поддерево q.enqueue(x.left); if (!

x.right.empty) // x.right — правое поддерево q.enqueue(x.right); }

Рекурсивные обходы можно, очевидно, организовать и с помощью стека, ‘развернув’ рекурсию.

.

Добавить комментарий

Закрыть меню