- Текущая
- В очереди
- Посещенные
- Путь
Поиск в ширину (BFS)
Поиск в ширину обходит граф кольцами: сначала все вершины рядом со стартом, потом все вершины в двух ребрах от него и так далее. Для этого он использует очередь: первым пришел — первым ушел. Щелкните вершину, чтобы начать с нее, при желании выберите цель и пройдите поиск по шагам: вы увидите, как очередь растет и уменьшается, как каждая вершина получает расстояние и как появляется кратчайший путь. Нажмите Пуск, чтобы посмотреть поиск, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Щелкните вершину, чтобы сделать ее стартом; переключите щелчок на Цель и щелкните другую вершину, чтобы искать кратчайший путь к ней. Число на каждой вершине — ее расстояние от старта, а ряд под графом — это очередь. Кнопка Новый граф создает другой граф; выберите, сколько в нем вершин и ребер. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.
Как это работает
- Щелкните вершину, чтобы сделать ее стартом. Чтобы искать путь, переключите щелчок на Цель и щелкните другую вершину.
- Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место поиска.
- Следите за очередью под графом и расстоянием на каждой вершине. Кнопка Новый граф создает другой граф для пробы.
Как работает поиск в ширину
Поместите стартовую вершину в очередь с расстоянием 0. Затем повторяйте: возьмите вершину из начала очереди и просмотрите всех ее соседей. Сосед, которого еще не видели, получает расстояние на единицу больше, чем у взятой вершины, запоминает эту вершину как ту, из которой в него пришли, и встает в конец очереди. Уже встречавшиеся соседи пропускаются. Когда очередь пуста, у каждой достижимой вершины есть расстояние.
Почему он находит кратчайшие пути
Очередь выдает вершины в том порядке, в котором они были найдены, а находятся они кольцо за кольцом: все вершины на расстоянии 1 попадают в очередь раньше любой на расстоянии 2 и так далее. Поэтому, когда вершина достигнута впервые, это сделано по пути с наименьшим возможным числом ребер. Если пройти по запомненным вершинам назад от цели к старту, получится этот путь. Здесь считаются только ребра; если у ребер разная длина, нужен алгоритм Дейкстры.
Часто задаваемые вопросы
Что такое поиск в ширину?
Способ обойти граф от стартовой вершины: сначала посетить всех ее соседей, потом их соседей и так далее, кольцо за кольцом. Очередь хранит вершины в том порядке, в котором они были найдены.
Находит ли поиск в ширину кратчайший путь?
Да, если все ребра равноценны: когда BFS впервые достигает вершины, он использует наименьшее возможное число ребер. Для ребер разной длины используйте алгоритм Дейкстры.
Чем BFS отличается от DFS?
Поиск в ширину использует очередь и расходится равномерно, кольцо за кольцом. Поиск в глубину использует стек (или рекурсию) и идет по одному пути как можно глубже, прежде чем вернуться. BFS находит кратчайшие пути по числу ребер; DFS нет, зато он удобен для поиска циклов и топологической сортировки.
Насколько быстр поиск в ширину?
Он извлекает каждую вершину из очереди один раз и просматривает каждое ребро с обоих концов, поэтому работа растет пропорционально сумме числа вершин и числа ребер.
Отправляется ли мой граф куда-нибудь?
Нет. Граф создается и обходится в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор