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

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

Чтобы получить более глубокие знания об искусственном интеллекте и машинном обучении, вы можете зарегистрироваться в прямом эфире от Edureka с поддержкой 24/7 и пожизненным доступом.

Вот список тем, которые будут освещены в этом блоге:

1. Введение в обход графа
2. Что такое поиск в ширину?
3. Понимание алгоритма поиска в ширину на примере
4. Псевдокод алгоритма поиска в ширину
5. Приложения поиска в ширину

Введение в обход графа

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

Звучит просто! Но есть загвоздка.

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

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

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

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

1. Посещение узла: Как следует из названия, посещение узла означает посещение или выбор узла.
2. Изучение узла: Изучение смежные узлы (дочерние узлы) выбранного узла.

Обратитесь к рисунку выше, чтобы лучше понять это.

Понимание алгоритма поиска в ширину на примере

создать параметр в таблице

Алгоритм поиска в ширину следует простому, основанному на уровнях подходу к решению проблемы. Рассмотрим приведенное ниже двоичное дерево (которое является графом). Наша цель - пройти по графу с помощью алгоритма поиска в ширину.

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

Очередь - это абстрактная структура данных, которая соответствует методологии «первым пришел - первым обслужен» (данные, вставленные первыми, будут доступны первыми). Он открыт с обеих сторон, причем один конец всегда используется для вставки данных (постановка в очередь), а другой - для удаления данных (постановка из очереди).

Теперь давайте посмотрим на шаги, необходимые для обхода графика с помощью поиска в ширину:

Шаг 1: Возьмите пустую очередь.

Шаг 2: Выберите начальный узел (посещение узла) и вставьте его в очередь.

Шаг 3: При условии, что Очередь не пуста, извлеките узел из Очереди и вставьте его дочерние узлы (исследуя узел) в Очередь.

Шаг 4: Распечатайте извлеченный узел.

Не волнуйтесь, если запутались, разберемся на примере.

вызов по ссылке c ++

Взгляните на график ниже, мы будем использовать алгоритм поиска в ширину, чтобы пройти по графику.

В нашем случае мы назначим узел «a» в качестве корневого узла, начнем движение вниз и выполним шаги, упомянутые выше.

На приведенном выше изображении показан сквозной процесс алгоритма поиска в ширину. Позвольте мне объяснить это более подробно.

1. Назначьте «a» корневым узлом и вставьте его в очередь.
2. Извлеките узел «a» из очереди и вставьте дочерние узлы «a», то есть «b» и «c».
3. Распечатать узел «а».
4. Очередь не пуста и имеет узлы «b» и «c». Поскольку «b» является первым узлом в очереди, давайте извлечем его и вставим дочерние узлы «b», то есть узлы «d» и «e».
5. Повторяйте эти шаги, пока очередь не станет пустой. Обратите внимание, что узлы, которые уже посещены, не должны добавляться в очередь. очередной раз.

Теперь давайте посмотрим на псевдокод алгоритма поиска в ширину.

Псевдокод алгоритма поиска в ширину

Вот псевдокод для реализации алгоритма поиска в ширину:

Вход: s в качестве исходного узла BFS (G, s) пусть Q будет очередью. Q.enqueue (s) помечает s как посещенное, в то время как (Q не пусто) v = Q.dequeue () для всех соседей w из v в Графике G, если w не посещается Q.enqueue (w) отмечает w как посещенное

В приведенном выше коде выполняются следующие шаги:

1. (G, s) вводится, здесь G - граф, а s - корневой узел
2. Очередь «Q» создается и инициализируется исходным узлом «s»
3. Все дочерние узлы 's' отмечены
4. Извлеките 's' из очереди и посетите дочерние узлы
5. Обработать все дочерние узлы v
6. Сохраняет w (дочерние узлы) в Q для дальнейшего посещения его дочерних узлов
7. Продолжайте, пока 'Q' не станет пустой

Прежде чем мы завершим блог, давайте рассмотрим некоторые применения алгоритма поиска в ширину.

Применение алгоритма поиска в ширину

Поиск в ширину - это простой метод обхода графа, который имеет удивительный диапазон приложений. Вот несколько интересных способов использования поиска «сначала хлеб»:

Сканеры в поисковых системах: Поиск в ширину - один из основных алгоритмов, используемых для индексации веб-страниц. Алгоритм начинает переход с исходной страницы и следует по всем ссылкам, связанным со страницей. Здесь каждая веб-страница будет рассматриваться как узел на графике.

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

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

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

Одноранговая сеть: Поиск в ширину может использоваться как метод обхода для поиска всех соседних узлов в одноранговой сети. Например, BitTorrent использует поиск в ширину для одноранговой связи.

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

3. Введение в цепи Маркова с примерами - цепи Маркова с Python

На этом мы подошли к концу этого блога. Если у вас есть вопросы по этой теме, оставьте комментарий ниже, и мы свяжемся с вами.

ng-change против onchange

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