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