Алгоритм поиска в ширину — это способ обхода графа и определения маршрутов внутри графа.
Введение
Под поиском в ширину понимается вид алгоритма обхода графа. Этот способ заложен также в основание и некоторого количества иных алгоритмов, которые близки по типу обработки информации. Поиск в ширину организует изучение графа по некоторым его уровням. Сначала изучается корневой уровень, которым может стать произвольно назначенный узел, далее производные (потомки) от этого узла, а затем выполняется посещение потомков, оставшихся от потомков и так далее. Обход вершин ведётся в очерёдности увеличения их удаления от корневого уровня.
Алгоритм поиска в ширину
Имеем граф 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 )
Полнота алгоритма
В случае, когда каждый узел имеет не бесконечное количество «потомков», то алгоритм будет считаться полным при условии:
- Существования решения и алгоритм поиска в ширину может его найти, не зависимо от конечности графа.
- Решение не существует, но если граф бесконечен, то поиск не будет завершён.
Если размеры рёбер графа одинаковые, то алгоритм поиска в ширину будет на уровне оптимального, так как гарантированно определит самый короткий маршрут.
