Алгоритм поиска в ширину (BFS) с примером
Сара Чен
⚡ Умное резюме
Поиск в ширину (BFS) — это алгоритм, который пошагово обходит граф, посещая всех соседей узла перед тем, как двигаться дальше. Он использует очередь FIFO и находит кратчайший путь в невзвешенных графах без бесконечных циклов.
Что такое алгоритм 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 – First in First Out – Первый вошел – Первый вышел) структура данных используется BFS.
- Вы помечаете любой узел в графе как корень и начинаете обход данных, начиная с него.
- Метод BFS обходит все узлы графа и продолжает удалятьping их в завершенном виде.
- BFS посещает соседний непосещенный узел, отмечает его как выполненный и вставляет в очередь.
- В случае, если не найдена смежная вершина, предыдущая вершина удаляется из очереди.
- Алгоритм BFS выполняет итерации до тех пор, пока все вершины графа не будут успешно пройдены и помечены как пройденные.
- При прохождении данных из любого узла из-за BFS не возникает петель.
Приложения алгоритма BFS
Давайте посмотрим на некоторые реальные приложения, в которых реализация алгоритма BFS может быть весьма эффективной.
- Невзвешенные графики: Алгоритм BFS позволяет легко построить кратчайший путь и минимальное остовное дерево, чтобы обойти все вершины графа за кратчайшее возможное время с высокой точностью.
- P2P-сети: Поиск в ширину (BFS) может быть использован для определения местоположения всех ближайших или соседних узлов в одноранговой сети. Это позволит быстрее находить необходимые данные.
- Веб-сканеры: Поисковые системы или веб-сканеры могут легко создавать несколько уровней индексов, используя BFS. Реализация BFS начинается с источника, которым является веб-страница, а затем посещаются все ссылки из этого источника.
- Навигационные системы: BFS может помочь найти все соседние локации из основной или исходной локации.
- Сетевое вещание: Широковещательный пакет управляется алгоритмом BFS для поиска и достижения всех узлов, для которых он имеет адрес.
