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

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

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

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

Белый — вершина, которая еще не обнаружена. Серый — вершина, уже обнаруженная и добавленная в очередь. Черный — вершина, извлечённая из очереди

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

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

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

1. Поместить узел, с которого начинается поиск, в изначально пустую очередь.
2. Извлечь из начала очереди узел $u$ и пометить его как развёрнутый.
   • Если узел $u$ является целевым узлом, то завершить поиск с результатом «успех».
   • В противном случае, в конец очереди добавляются все преемники узла $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;                        // Целевой узел недостижим
}

Примеры реализации

Python

BFS(s,Adj):
  level = { s: 0 }
  parent = { s: None }
  i = 1
  frontier = [s]
  while frontier:
    next = []
    for u in frontier:
      for v in Adj[u]:
        if v not in level:
          level[v] = i
          parent[v] = u
          next.append(v)
    frontier = next
    i += 1

PHP

$graph = array( 'A' => array('B','C','D','Z'), 'B' => array('A','E'), 'C' => array('A','F','G'), 'D' => array('A','I'), 'E' => array('B','H'), 'F' => array('C','J'), 'G' => array('C'), 'H' => array('E','Z'), 'I' => array('D'), 'J' => array('J'), 'Z' => array('A','H'));

function bfs($graph , $startNode = 'A')
{
  $visited = array();
  $queue = array();
		
  $queue[] = $graph[$startNode];
  $visited[$startNode] = true;
		
  while( count($queue) > 0 )
  {
    $currentNodeAdj = array_pop($queue);

    foreach($currentNodeAdj as $vertex)
    {
      if(!array_key_exists($vertex,$visited))
      {
        array_unshift( $queue , $graph[$vertex] ) ;
      }

      $visited[$vertex] = true;
    }
  }
}

Свойства

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

Пространственная сложность

Так как в памяти хранятся все развёрнутые узлы, пространственная сложность алгоритма составляет $O(\vert V\vert +\vert E\vert )$.

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

Временная сложность

Так как в худшем случае алгоритм посещает все узлы графа, при хранении графа в виде списков смежности, временная сложность алгоритма составляет $O(\vert V\vert +\vert E\vert )$.

Полнота

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

Оптимальность

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

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

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

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

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

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

См. также

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

Литература

• 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. Метод уменьшения размера задачи: Поиск в ширину // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: Вильямс, 2006. — С. 215-218. — ISBN 0-201-74395-7.

Ссылки

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