Алгоритм поиска в ширину (BFS) с примером

Что такое алгоритм BFS (поиск в ширину)?

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

Алгоритм эффективно посещает и маркирует все ключевые узлы графа с точностью по ширине. Этот алгоритм выбирает один узел (начальную или исходную точку) на графе, а затем посещает все узлы, соседние с выбранным узлом. Помните, что BFS обращается к этим узлам один за другим.

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

Что такое обход графа?

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

Архитектура алгоритма BFS

На различных уровнях данных вы можете пометить любой узел как начальный или начальный узел для начала перемещения. BFS посетит узел, пометит его как посещенный и поместит в очередь.
Теперь BFS посетит ближайшие и непосещенные узлы и отметит их. Эти значения также добавляются в очередь. Очередь работает на Модель ФИФО.
Аналогичным образом анализируются оставшиеся ближайшие и непосещенные узлы графа, которые отмечаются и добавляются в очередь. Эти элементы удаляются из очереди по мере получения и печатаются в результате.

Зачем нам нужен алгоритм BFS?

Существует множество причин использовать алгоритм BFS для поиска вашего набора данных. Вот некоторые из наиболее важных аспектов, которые делают этот алгоритм вашим первым выбором:

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

Как работает алгоритм BFS?

Обход графа требует, чтобы алгоритм посещал, проверял и/или обновлял каждый непосещенный узел в древовидной структуре. Обходы графа классифицируются по порядку, в котором они посещают узлы графа.

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

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

Шаг 1)

Каждая вершина или узел графа известна. Например, вы можете пометить узел как V.

Шаг 2)

Если к вершине V нет доступа, добавьте вершину V в очередь BFS.

Шаг 3)

Запустите поиск BFS и после завершения отметьте вершину V как посещенную.

Шаг 4)

Очередь BFS все еще не пуста, поэтому удалите вершину V графа из очереди.

Шаг 5)

Получить все оставшиеся вершины графа, смежные с вершиной V.

Шаг 6)

Для каждой соседней вершины, скажем, V1, если она еще не посещена, добавьте V1 в очередь BFS.

Шаг 7)

BFS посетит V1, отметит его как посещенный и удалит из очереди.

Пример алгоритма BFS

Шаг 1)

У вас есть график из семи чисел в диапазоне от 0 до 6.

Шаг 2)

0 или ноль был помечен как корневой узел.

Шаг 3)

0 посещается, помечается и вставляется в структуру данных очереди.

Шаг 4)

Остальные 0 соседних и непосещенных узлов посещаются, помечаются и вставляются в очередь.

Шаг 5)

Итерации обхода повторяются до тех пор, пока не будут посещены все узлы.

Правила алгоритма BFS

Вот важные правила использования алгоритма BFS:

Очередь (FIFO — «первым пришел — первым обслужен») структура данных используется BFS.
Вы отмечаете любой узел графа как корневой и начинаете просматривать данные из него.
BFS обходит все узлы графа и продолжает удалять их как завершенные.
BFS посещает соседний непосещенный узел, отмечает его как выполненный и вставляет в очередь.
Удаляет предыдущую вершину из очереди, если соседняя вершина не найдена.
Алгоритм BFS выполняет итерации до тех пор, пока все вершины графа не будут успешно пройдены и не отмечены как завершенные.
При прохождении данных из любого узла из-за BFS не возникает петель.

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

Давайте посмотрим на некоторые реальные приложения, в которых реализация алгоритма BFS может быть весьма эффективной.

Невзвешенные графики: Алгоритм BFS может легко создать кратчайший путь и минимальное связующее дерево для посещения всех вершин графа в кратчайшие сроки с высокой точностью.
P2P-сети: BFS может быть реализована для обнаружения всех ближайших или соседних узлов в одноранговой сети. Это позволит быстрее найти необходимые данные.
Веб-сканеры: Поисковые системы или веб-сканеры могут легко создавать несколько уровней индексов, используя BFS. Реализация BFS начинается с источника, которым является веб-страница, а затем посещаются все ссылки из этого источника.
Навигационные системы: BFS может помочь найти все соседние локации из основной или исходной локации.
Сетевое вещание: Широковещательный пакет управляется алгоритмом BFS для поиска и достижения всех узлов, для которых он имеет адрес.

Резюме

Обход графа — это уникальный процесс, который требует, чтобы алгоритм посещал, проверял и/или обновлял каждый непосещенный узел в древовидной структуре. Алгоритм BFS работает по аналогичному принципу.
Алгоритм полезен для анализа узлов графа и построения кратчайшего пути прохождения через них.
Алгоритм обходит граф за наименьшее количество итераций и за минимально возможное время.
BFS выбирает один узел (начальную или исходную точку) на графике, а затем посещает все узлы, соседние с выбранным узлом. BFS обращается к этим узлам один за другим.
Посещенные и отмеченные данные помещаются в очередь BFS. Очередь работает по принципу «первым пришел — первым обслужен». Следовательно, элемент, помещенный в график первым, сначала удаляется и в результате печатается.
Алгоритм BFS никогда не может попасть в бесконечный цикл.
Благодаря высокой точности и надежной реализации BFS используется во многих реальных решениях, таких как P2P-сети, веб-сканеры и сетевое вещание.