Алгоритм поиска в ширину — это способ обхода графа и определения маршрутов внутри графа.
Введение
Под поиском в ширину понимается вид алгоритма обхода графа. Этот способ заложен также в основание и некоторого количества иных алгоритмов, которые близки по типу обработки информации. Поиск в ширину организует изучение графа по некоторым его уровням. Сначала изучается корневой уровень, которым может стать произвольно назначенный узел, далее производные (потомки) от этого узла, а затем выполняется посещение потомков, оставшихся от потомков и так далее. Обход вершин ведётся в очерёдности увеличения их удаления от корневого уровня.
Алгоритм поиска в ширину
Имеем граф G = (V, Е) и корневой уровень S, выбранный для начала обхода. Первым посещается узел S, а затем выполняется посещение смежных с S узлов (множество узлов, которые являются смежными с S, обозначим символом q; подразумевается, что q ⊆ V, то есть q является неким подмножеством V). В дальнейшем такая операция повторяется для всех вершин, которые смежные с множеством вершин q, исключая вершину s, поскольку её уже посещали. Таким образом, выполняется поочерёдный последовательный обход всех уровней до момента прохождения всех достижимых из s вершин множества V. Выполнение алгоритма прекращается по завершению анализа всего графа, или если будет выполнено заданное условие.
Рассмотрим пример, где предполагаем, что при выполнении алгоритма каждая из вершин графа может быть покрашена в одну из трёх расцветок: серую, белую или чёрную. Но исходный цвет всех вершин, белый. При обходе каждая вершина, которая была обнаружена, подлежит окрашиванию первоначально в серый, а потом в чёрный цвет. Каждый текущий период обхода может быть описан таким образом: если цвет вершины чёрный, то все её «потомки» могут иметь или серые, или чёрные цвета. Итак, есть смешанный граф с |V| = 4 и |E| = 5, представленный на рисунке один. Необходимо пройти все его вершины, применяя алгоритм поиска в ширину. Выберем как корневую (стартовую) вершину, узел с номером три. Вначале его надо покрасить в серый цвет, поскольку он считается обнаруженным, а потом в чёрный, так как обнаруживаются смежные с ним вершины один и четыре, которые также согласно очерёдности окрашиваются в серый цвет. Далее чёрный цвет получает вершина один, и определяются его соседние вершины. Это узел два, который надо покрасить в серый цвет. И, в конечном итоге, вершины четыре и два, осматриваются в этой очерёдности и на этом обход в ширину заканчивается.
Рисунок 1. Смешанный граф. Автор24 — интернет-биржа студенческих работ
Способ поиска в ширину возможно применять как с ориентированными графами, так и с неориентированными. Эту возможность поиска в ширину можно увидеть, если применить его на смешанном графе, что и показано выше. Заметим, что если это неориентированный связной граф, то поиск в ширину должен пройти все вершины, но если это смешанный граф, то этого может и не быть. И ещё, мы рассматривали обход всех узлов (вершин), но есть вероятность, что хватит обхода некоторого их числа, или поиска какой-либо определённой вершины. В таком случае надо немного модернизировать алгоритм поиска, но не менять его целиком или отказываться от его применения.
Формализация поиска в ширину
Основными объектными структур информационных данных, применяемых в программе, являются:
- Матрица смежности GM.
- Формирование очереди quеuе.
- Формирование массива посещённых вершин (visitеd).
Два первых пункта представляют собой данные, состоящие из целых чисел, а третий тип является чисто логические данные. Вершины, которые уже посещались, необходимо занести в массив visitеd, чтобы избежать зацикливания программы, а в очереди queuе сохраняются участвующие в поиске вершины. Следует помнить, что данные типа «очередь» действуют по методике «первым пришёл, первым и вышел». Очерёдность действий при обходе графа, следующая:
- Обнуление массива visitеd, то есть нет посещённых вершин графа.
- Выполняется выбор стартовой вершины s и её помещают в очередь в соответствующий массив.
- Выполняется исследование вершины s, она получает метку «посещённая», и все вершины, которые являются смежными с ней, перемещаются в хвост очереди, а вершина s подлежит удалению.
- Если окажется, что на этом шаге очередь уже нулевая, то выполнение алгоритма прекращается, в ином случае выполняется посещение вершины, стоящей первой в очереди, делается отметка о её посещении, а все её «потомственные» вершины ставятся в конец очереди.
- Пока есть возможность, производится выполнение пункта четыре.
Алгоритм поиска в ширину начинается со стартовой вершины и постоянно удаляется от неё, обходя один уровень за другим. В итоге, по завершению выполнения алгоритма, определены все самые короткие маршруты из стартовой вершины до всех достижимых из неё вершин.
Чтобы реализовать алгоритм поиска в ширину программными средствами, необходимо уметь определять граф и формировать список очереди. Эти возможности есть практически во всех современных языках программирования.
Пространственная и временная сложность
Поскольку в памяти сохраняются все использованные узлы, то сложность в пространстве этого алгоритма будет иметь следующий вид:
{\displaystyle O (\vert V\vert +\vert E\vert )}O(\vert V\vert +\vert E\vert)
С точки зрения временной сложности наихудшим случаем будет посещение всех узлов графа. Если граф сохраняется в форме списков смежности, то временная сложность поиска в ширину будет:
{\displaystyle O (\vert V\vert +\vert E\vert )}O(\vert V\vert +\vert E\vert )
Полнота алгоритма
В случае, когда каждый узел имеет не бесконечное количество «потомков», то алгоритм будет считаться полным при условии:
- Существования решения и алгоритм поиска в ширину может его найти, не зависимо от конечности графа.
- Решение не существует, но если граф бесконечен, то поиск не будет завершён.
Если размеры рёбер графа одинаковые, то алгоритм поиска в ширину будет на уровне оптимального, так как гарантированно определит самый короткий маршрут.
