«Обход в ширину» или «Поиск в ширину» (Breadth first traversal or Breadth first Search) - это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. Для простоты предполагается, что все вершины достижимы из начальной вершины. BFS использует для обхода структуру данных: очередь (queue) Стандартная реализация ВFS помещает каждую вершину графа в одну из двух категорий: Цель алгоритма - пометить каждую вершину, как посещенную, избегая циклов. Алгоритм работает следующим образом: Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере...

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