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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Поиск в ширину

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

Работа алгоритма[править | править вики-текст]

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

Поиск в ширину работает путём последовательного просмотра отдельных уровней графа, начиная с узла-источника 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_nodefringe) {
    return true;
  }
  return BFS'({child | xfringe, child ∈ expand(x)} \ visited, visitedfringe, 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)[1].

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

Временная сложность[править | править вики-текст]

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

Полнота[править | править вики-текст]

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

Оптимальность[править | править вики-текст]

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

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

История и применения[править | править вики-текст]

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 3 4 5 6 MAXimal :: algo :: Поиск в ширину в графе и его приложения
  2. 1 2 НГТУ Структуры и алгоритмы обработки данных Обход графа в ширину
  3. 1 2 E. F. Moore (1959), The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, pp. 285–292.
  4. 1 2 C. Y. Lee (1961), An algorithm for path connection and its applications. IRE Transactions on Electronic Computers, EC-10(3), pp. 346–365
  5. Cormen et al, Introduction to Algorithms, 3rd edition, p. 623
  6. Mathematics Stack Exchange Origin of the Breadth-First Search algorithm

Литература[править | править вики-текст]

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein Introduction to Algorithms. — 3rd 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

Ссылки[править | править вики-текст]