Поиск в ширину

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

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

Поиск в ширину является одним из неинформированных алгоритмов поиска.

Работа алгоритма 

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

Рассмотрим все рёбра , выходящие из узла . Если очередной узел  является целевым узлом, то поиск завершается; в противном случае узел  добавляется в очередь. После того, как будут проверены все рёбра, выходящие из узла , из очереди извлекается следующий узел , и процесс повторяется.

Неформальное описание 
 Поместить узел, с которого начинается поиск, в изначально пустую очередь.
 Извлечь из начала очереди узел  и пометить его как развёрнутый.
 Если узел  является целевым узлом, то завершить поиск с результатом «успех».
 В противном случае, в конец очереди добавляются все преемники узла , которые ещё не развёрнуты и не находятся в очереди.
 Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
 Вернуться к п. 2.
Примечание: деление вершин на развёрнутые и не развёрнутые необходимо для произвольного графа (так как в нём могут быть циклы). Для дерева эта операция не нужна, так как каждая вершина будет выбрана один-единственный раз.

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

Рекурсивная формулировка:
 BFS(start_node, goal_node) {
   return BFS'({start_node}, ∅, goal_node);
 }
 BFS'(fringe, visited, goal_node) {
   if(fringe == ∅) {
     // Целевой узел не найден
     return false; 
   }
   if (goal_node ∈ fringe) {
     return true;
   }
   return BFS'({child | x ∈ fringe, child ∈ expand(x)} \ visited, visited ∪ fringe, goal_node);
 }

Итеративная формулировка:
 BFS(start_node, goal_node) {
  for(all nodes i) visited[i] = false; // изначально список посещённых узлов пуст
  queue.push(start_node);              // начиная с узла-источника
  while(! queue.empty() ) {            // пока очередь не пуста
   node = queue.pop();                 // извлечь первый элемент в очереди
   if(node == goal_node) {
    return true;                       // проверить, не является ли текущий узел целевым
   }
   visited[node] = true;               // пометить текущую ноду посещенной
   foreach(child in expand(node)) {    // все преемники текущего узла, ...
    if(visited[child] == false) {      // ... которые ещё не были посещены ...
     queue.push(child);                // ... добавить в конец очереди...
     visited[child] = true;            // ... и пометить как посещённые
    }
   }
  }
  return false;                        // Целевой узел недостижим
 }

Реализация на Pascal:

function BFS(v : Node) : Boolean;
begin
  enqueue(v);
  while queue is not empty do
  begin
    curr := dequeue();
    if is_goal(curr) then
    begin
      BFS := true;
      exit;
    end;
    mark(curr);
    for next in successors(curr) do
      if not marked(next) then
      begin
        enqueue(next);
      end;
  end;
  BFS := false;
end;

Свойства 
Обозначим число вершин и рёбер в графе как  и  соответственно.

Пространственная сложность 
Так как в памяти хранятся все развёрнутые узлы, пространственная сложность алгоритма составляет .

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

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

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

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

Поиск по критерию стоимости является обобщением поиска в ширину и оптимален на взвешенном графе с неотрицательными весами рёбер. Алгоритм посещает узлы графа в порядке возрастания стоимости пути из начального узла и обычно использует очередь с приоритетами.

История и применения 
Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте. Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах.

Поиск в ширину может применяться для решения задач, связанных с теорией графов:
 Волновой алгоритм поиска пути в лабиринте
 Волновая трассировка печатных плат
 Поиск компонент связности в графе
 Поиск кратчайшего пути между двумя узлами невзвешенного графа
 Поиск в пространстве состояний: нахождение решения задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа
 Нахождение кратчайшего цикла в ориентированном невзвешенном графе
 Нахождение всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами  и 
 Поиск увеличивающего пути в алгоритме Форда-Фалкерсона (алгоритм Эдмондса-Карпа)

См. также 

 Поиск с ограничением глубины
 Поиск в глубину
 Алгоритм Дейкстры

Примечания

Литература 
 . Перевод 2-го издания:

Ссылки 

 Steven M. Rubin Computer Aids for VLSI Design. Chapter 4: Synthesis Tools
 Волновой алгоритм поиска пути
 Поиск в ширину на Pascal и C++

Алгоритмы поиска на графах
Алгоритмы поиска