Алгоритм поиска в ширину: обзор, важность и применение

Графики вокруг нас. Граф можно рассматривать как взаимосвязанную сеть узлов и ребер. Ваши друзья на Facebook, ваши связи в LinkedIn или ваши подписчики в Twitter/Instagram составляют ваш социальный график. Точно так же, если вы хотите добраться из точки А в точку Б, вы можете сделать это по нескольким маршрутам, которые можно визуализировать на Картах Google.

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

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

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

В этой статье мы подробно рассмотрим алгоритм поиска в ширину или BFS.

Структура графика

Прежде чем мы подробно заглянем под капот BFS, давайте познакомимся с некоторыми терминами графов с помощью приведенного выше графика:

Корневой узел — узел, с которого вы начинаете процесс обхода. Для простоты мы можем считать A корневым узлом.

Уровни . Уровень — это совокупность всех узлов, равноудаленных от корневого узла. Итак, если мы считаем, что узел A находится на уровне 0, узлы B и C находятся на уровне 1, а узлы D, E и F — на уровне 2. Простая эвристика для определения номера уровня узла состоит в том, чтобы подсчитать число ребер между указанным узлом и корневым узлом. Обратите внимание, что это работает, только если вы определяете корневой узел на уровне 0.

Родительский узел . Родительским узлом узла является тот, который находится на один уровень выше него и примыкает к нему. Его можно рассматривать как узел, из которого происходит указанный узел. A является родительским узлом B и C.

Дочерние / дочерние узлы — узлы, которые ответвляются и примыкают к родительскому узлу. B и C являются дочерними узлами A

Читайте: 10 лучших методов визуализации данных

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

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

Давайте посмотрим на подробные операции с очередью для алгоритма BFS для приведенного выше графа:

() – обозначает очередь

[] — обозначает вывод на печать

1. Вставьте A в очередь (a)
2. Распечатайте A, вставьте B и C в очередь (cb)[a]
3. Выведите B, вставьте его дочерние узлы D и E в очередь (edc)[ba]
4. Распечатайте C, вставьте его дочерний узел F в очередь (fed)[cba]
5. Выведите D, вставьте его дочерний узел в очередь. Их нет. (fe) [dcba]
6. Выведите E, чей дочерний узел F уже вставлен в очередь. (е) [edcba]
7. Печать F. [fedcba]

Что делает алгоритм BFS важным

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

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

Оформить заказ: проекты визуализации данных, которые вы можете воспроизвести

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

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

Сканеры поисковых систем — попробуйте представить мир без Google или Bing. Вы не можете. Поисковые системы являются основой Интернета. Алгоритм BFS является основой поисковых систем. Это основной алгоритм, используемый для индексации веб-страниц. Алгоритм начинает свой путь с исходной страницы (корневой узел), а затем следует по всем ссылкам на этой исходной странице по ширине. Каждую веб-страницу можно рассматривать как независимый узел графа.

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

GPS-навигация — BFS использует системы GPS для обнаружения всех возможных соседних местоположений от вашей начальной точки, помогая вам беспрепятственно перемещаться из точки А в точку Б.

Широковещательная передача — широковещательная сеть использует пакеты в качестве единиц для передачи сигналов и данных. Алгоритм BFS направляет эти пакеты ко всем узлам в сети, которых они должны достичь.

Сети P2P . Торренты или другие сети для обмена файлами полагаются на связь P2P. BFS отлично работает, чтобы найти ближайшие узлы, чтобы передача данных могла происходить быстрее.

Читайте также: Преимущества визуализации данных

Заключение

Следовательно, алгоритм поиска в ширину — один из самых важных алгоритмов современного Интернета. Надеюсь, этот блог послужит удобной отправной точкой в ​​ваших исследованиях алгоритмов поиска.

Мы рекомендуем вам выбрать диплом PG по науке о данных, предлагаемый IIIT Bangalore, размещенный на upGrad, потому что здесь вы можете получить свои вопросы 1-1 с преподавателями курса. Он фокусируется не только на теоретическом обучении, но и придает большое значение практическим знаниям, которые необходимы для подготовки учащихся к работе с реальными проектами и предоставления вам первого в Индии сертификата NASSCOM, который поможет вам получить высокооплачиваемую работу в науке о данных.