Посещенные
В очереди
Проверенные ребра

  • Текущая
  • В очереди
  • Посещенные
  • Путь
Щелчок по вершине задает

Подробнее о поиске в ширину

Поиск в ширину (BFS)

Поиск в ширину обходит граф кольцами: сначала все вершины рядом со стартом, потом все вершины в двух ребрах от него и так далее. Для этого он использует очередь: первым пришел — первым ушел. Щелкните вершину, чтобы начать с нее, при желании выберите цель и пройдите поиск по шагам: вы увидите, как очередь растет и уменьшается, как каждая вершина получает расстояние и как появляется кратчайший путь. Нажмите Пуск, чтобы посмотреть поиск, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Щелкните вершину, чтобы сделать ее стартом; переключите щелчок на Цель и щелкните другую вершину, чтобы искать кратчайший путь к ней. Число на каждой вершине — ее расстояние от старта, а ряд под графом — это очередь. Кнопка Новый граф создает другой граф; выберите, сколько в нем вершин и ребер. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.

Как это работает

  1. Щелкните вершину, чтобы сделать ее стартом. Чтобы искать путь, переключите щелчок на Цель и щелкните другую вершину.
  2. Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место поиска.
  3. Следите за очередью под графом и расстоянием на каждой вершине. Кнопка Новый граф создает другой граф для пробы.

Как работает поиск в ширину

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

Почему он находит кратчайшие пути

Очередь выдает вершины в том порядке, в котором они были найдены, а находятся они кольцо за кольцом: все вершины на расстоянии 1 попадают в очередь раньше любой на расстоянии 2 и так далее. Поэтому, когда вершина достигнута впервые, это сделано по пути с наименьшим возможным числом ребер. Если пройти по запомненным вершинам назад от цели к старту, получится этот путь. Здесь считаются только ребра; если у ребер разная длина, нужен алгоритм Дейкстры.

Часто задаваемые вопросы

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

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

Находит ли поиск в ширину кратчайший путь?

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

Чем BFS отличается от DFS?

Поиск в ширину использует очередь и расходится равномерно, кольцо за кольцом. Поиск в глубину использует стек (или рекурсию) и идет по одному пути как можно глубже, прежде чем вернуться. BFS находит кратчайшие пути по числу ребер; DFS нет, зато он удобен для поиска циклов и топологической сортировки.

Насколько быстр поиск в ширину?

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

Отправляется ли мой граф куда-нибудь?

Нет. Граф создается и обходится в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор