Алгоритм обхода в ширину

Введение

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

Алгоритм поиска в ширину можно применять для ориентированных и неориентированных графов. Термин поиск в ширину образовался потому, что при проходе вершин постоянно расширяется зона их охвата, то есть прежде чем начать искать вершины на удалении К+1, осуществляется проход вершин на удалении К.

Практическая реализация алгоритма обхода в ширину

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


В данной программе под g обозначен перечень смежных вершин. То есть в массиве g[u] находится перечень вершин, которые являются смежными с u. А used является массивом, со списком уже посещённых вершин. То есть в программе в чистом виде заложен только лишь сам обход в ширину. Но алгоритм можно модифицировать и искать попутно дистанцию и маршрут от заданной вершины до всех других вершин. Отметим, так же, что в этом примере рассматривается не взвешенный граф, то есть его рёбра не обладают весами. Ниже приведена программа определения дистанций и маршрутов:

Рисунок 1. Программа. Автор24 — интернет-биржа студенческих работ

Где р является массивом предков, то есть в массиве p[v] находится предок вершины v, а dist[v] будет расстоянием от начальной вершины обхода до вершины V. Но ещё необходимо выполнить восстановление маршрута. Делается это просто, нужно выполнить проход через массив предков требуемой вершины. Возможно использовать рекурсию:

Рисунок 2. Рекурсия. Автор24 — интернет-биржа студенческих работ

Определение кратчайших путей

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

Рисунок 3. Программа. Автор24 — интернет-биржа студенческих работ

По сути, этот алгоритм аналогичен алгоритму Левита, но всё-таки с некоторыми отличиями. В самом плохом случае необходимо выполнять релаксацию всегда, когда выполняется проход по какому-то ребру. Итоговая сложность тогда будет O(n • m). Но следует ещё раз подчеркнуть, что это в самом плохом случае, а при практической реализации получается достаточно хорошее быстродействие. Дальнейшим улучшением алгоритма обхода в ширину является алгоритм Дейкстры.

Алгоритм Дейкстры

Если выполнять релаксацию тех вершин, путевой маршрут до которых самый маленький, то это и будет сутью алгоритма известного учёного Эдсгера Дейкстры. Кроме того, он сумел доказать, что если выбирать вершину для релаксации таким методом, то суммарное количество релаксаций не будет превышать n раз. Интуитивно понятно, что если путь до какой-либо вершины уже самый короткий, то его невозможно уменьшить. Для эффективного поиска вершины с самым маленьким расстояние до неё, можно привлечь методику кучи. Ниже приведена программная реализация алгоритма:

Рисунок 4. Программа. Автор24 — интернет-биржа студенческих работ

В качестве первого аргумента шаблона выступают данные, хранящиеся в очереди, а точнее числовые пары в виде дистанции до вершины и номера вершины. Вторым аргументом шаблона является по сути контейнер, сохраняющий данные, а третьим аргументом будет компаратор, который расположен в файле заголовка functional. Всего будет выполнено n релаксаций, и вершина, с самым коротким путевым расстоянием до неё, будет найдена за log(n). Необходимо также отметить, что возможен вариант, когда в очередь будет добавлена одна и та же вершина, но пути до неё различные. К примеру, была выполнена релаксация из вершины А, имеющая в качестве соседней вершину С, а затем выполнялась релаксация из вершины В, которая тоже имеет соседней вершиной ту же вершину С. Чтобы избежать возникновение такой проблемы, необходимо пропустить те вершины, которые брались из очереди, но дистанция до которых превышает текущее самое короткое расстояние. Эту операцию выполняет строка, имеющаяся в программе: if (u.first > dist[u.second]) continue;.

Сфера применения алгоритма обхода в ширину

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

1. Алгоритм определения путей в лабиринте, построенный на волновом принципе.
2. Выполнение трассировки печатных плат, построенной на волновом принципе.
3. Обнаружение компонент связности графа.
4. Определение минимального путевого маршрута между парой узлов невзвешенного графа.