Поиск в ширину — алгоритм поиска на графе.

Если задан граф G = (V, E) и начальную вершину s, алгоритм поиска в ширину систематически обходит все достижимые с s вершины. На первом этапе вершина s обозначается, как пройдена, а в список добавляются все вершины, достижимые из s без посещения промежуточных вершин. На каждом следующем шаге все текущие вершины списка отмечаются, как пройдены, а новый список формируется из вершин, которые являются еще не пройденными соседями текущих вершин списка. Для реализации списка вершин чаще всего используется очередь. Выполнение алгоритма продолжается до достижения искомой вершины или до тех пор, когда на определенном этапе в список включается одна вершина. Второй случай означает, что все вершины, доступные с начальной, уже отмеченные, как пройдены, а путь к целевой вершины не найден.

Алгоритм называется поиска в ширину, так как «фронт» поиска (между пройденными и непройденными вершинами) однообразно расширяется вдоль всей своей ширины. То есть, алгоритм проходит все вершины на расстоянии k перед тем как пройти вершины на расстоянии k 1.

Алгоритм

Приведем шаги алгоритма

  1. Начнем с произвольной вершины v. Выполнить BFS (v) = 1. Включить вершину v в очередь.
  2. Рассмотреть вершину, которая находится в начале очереди; пусть это будет вершина х. Если для всех вершин, смежных с вершиной х, уже определено BFS-номера, то перейти к шагу 4, иначе — к шагу 3.
  3. Пусть {x, y} — ребро, в котором номер BFS (в) не определено. Отметить это ребро утолщенной сплошной линией, определить BFS (в) как очередной BFS-номер, включить вершину в в очередь и перейти к шагу 2.
  4. Исключить вершину х с очереди. Если очередь пуста, то остановиться, иначе — перейти к шагу 2.

Источники информации

  1. а бы Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives t, Clifford Stein (2001). 22.2. Introduction to Algorithms (англ.) (Изд. 2-е). MIT Press. с. 531. ISBN 0-262-03293-7.

Изображения по теме

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