Поиск в ширину является базисным алгоритмом, составляющий основу многих других (алгоритм Дейкстры поиска кратчайших путей из одной вершины, алгоритм Прима поиска минимального покрывающего дерева)
Пусть задан граф G=(V,E) и фиксированная начальная вершина s.
Алгоритм поиска в ширину перечисляет все достижимые из вершины в порядке возрастания расстояния от s.
Расстояние – число ребер кратчайшего пути.
В процессе поиска из графа выделяется часть, называемая «деревом поиска в ширину» с корнем s. Она содержит все достижимые из s вершины. Путь из корня в дереве поиска до каждой из вершин в дереве поиска будет одним из кратчайших путей в графе.
Алгоритм применим и к ориентированным и к неориентированным графам.
Для вершин графа используется окраска – они могут быть белыми, серыми и черными.
Вначале все вершины белые.
В ходе работы белая вершина может стать серой, а серая – черной.
Окрашенные вершины (серые и черные) – уже обнаруженные в ходе поиска вершины.
Только серые вершины могут иметь смежные еще не обнаруженные вершины.
Вначале дерево поиска состоит только из корня – начальной вершины s. Как только алгоритм обнаруживает новую белую вершину v, смежную с ранее найденной вершиной u, вершина v вместе с ребром (u,v) добавляется к дереву поиска. Каждая вершина обнаруживается только однажды.
Процедура BFS (поиск в ширину) использует представление графа G=(V,E) списками смежных вершин. Для каждой вершины u графа дополнительно хранятся ее цвет color[u] и ее предшественник p[u]. Если предшественника нет p[u] = NIL.
Кроме того расстояние от s до u записывается в поле d[u].
Процедура использует очередь Q для хранения множества серых вершин.
head [Q] – указатель головы очереди;
ENQUEUE (Q,x) – процедура добавления элемента x в Q
DEQUEUE (Q) –процедура удаления элемента из Q
BFS (G,s)
1 for (для) каждой вершины u Î V[G] – {s}
2 do color[u] ¬БЕЛЫЙ
3 d[u] ´
4 p[u] ¬ NIL
5 color[s] ¬СЕРЫЙ
6 d[s] ¬ 0
7 p[s] ¬ NIL
8 Q ¬ {s}
9 while Q ¹ Æ
10 do u ¬ head [Q]
11 for (для) всех v Î Adj [u]
12 do if colour [v] = БЕЛЫЙ
13 then color [v] ¬ СЕРЫЙ
14 d [v] ¬ d[u] +1
15 p[v] ¬ u
16 ENQUEUE (Q,v)
17 DEQUEUE (Q)
18 colour[u] ¬ ЧЕРНЫЙ