WikiSort.ru - Программирование

Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из неинформированных алгоритмов поиска^[1].

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

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

Рассмотрим все рёбра ${\displaystyle (u,v)}$ , выходящие из узла ${\displaystyle u}$ . Если очередной узел ${\displaystyle v}$ является целевым узлом, то поиск завершается; в противном случае узел ${\displaystyle v}$ добавляется в очередь. После того, как будут проверены все рёбра, выходящие из узла ${\displaystyle u}$ , из очереди извлекается следующий узел ${\displaystyle u}$ , и процесс повторяется.

Неформальное описание

1. Поместить узел, с которого начинается поиск, в изначально пустую очередь.
2. Извлечь из начала очереди узел ${\displaystyle u}$ и пометить его как развёрнутый.
   • Если узел ${\displaystyle u}$ является целевым узлом, то завершить поиск с результатом «успех».
   • В противном случае, в конец очереди добавляются все преемники узла ${\displaystyle u}$ , которые ещё не развёрнуты и не находятся в очереди.
3. Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
4. Вернуться к п. 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);              // начиная с узла-источника
 visited[start_node] = true;
 while(! queue.empty() ) {            // пока очередь не пуста
  node = queue.pop();                 // извлечь первый элемент в очереди
  if(node == goal_node) {
   return 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;

Свойства

Обозначим число вершин и рёбер в графе как ${\displaystyle \vert V\vert }$ и ${\displaystyle \vert E\vert }$ соответственно.

История и применения

Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте^[3]. Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах^[4][5][6].

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

• Волновой алгоритм поиска пути в лабиринте^[3]
• Волновая трассировка печатных плат^[4]
• Поиск компонент связности в графе
• Поиск кратчайшего пути между двумя узлами невзвешенного графа
• Поиск в пространстве состояний: нахождение решения задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа^[1]
• Нахождение кратчайшего цикла в ориентированном невзвешенном графе^[1]
• Нахождение всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами ${\displaystyle a}$ и ${\displaystyle b}$ ^[1]
• Поиск увеличивающего пути в алгоритме Форда-Фалкерсона (алгоритм Эдмондса-Карпа)

См. также

Имеется викиучебник по теме
«Примеры реализации поиска в ширину»

• Поиск с ограничением глубины

Примечания

Литература

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. — 3^rd edition. — The MIT Press, 2009. — ISBN 978-0-262-03384-8.. Перевод 2-го издания: Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
• Левитин А. В. Глава 5. Метод уменьшения размера задачи: Поиск в ширину // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — 576 с. — ISBN 978-5-8459-0987-9
  <a href='https://wikidata.org/wiki/Track:Q21694518'></a><a href='https://wikidata.org/wiki/Track:Q21694521'></a><a href='https://wikidata.org/wiki/Track:Q21694522'></a>

Ссылки

	Поиск в ширину на Викискладе

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