Изменения
→Реализация
Приведенная ниже процедура поиска в ширину '''BFS''' предполагает, что входной граф <tex>G = (V, E)</tex> представлен при помощи списков смежности. Кроме того, поддерживаются дополнительные структуры данных в каждой вершине графа. Цвет каждой вершины <tex>u \in V</tex> хранится в переменной <tex>color[u]</tex>, а предшественник — в переменной <tex>p[u]</tex>. Если предшественника у <tex>u</tex> нет, то <tex>p[u] =</tex> NIL. Расстояние от <tex>s</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, хранится в поле <tex>d[u]</tex>. Алгоритм использует очередь <tex>Q</tex> для работы с множеством серых вершин.
'''BFS'''(<tex>G</tex>, <tex>s</tex>)
1 '''for''' (для) каждой вершины <tex>u \in V[G] - s</tex>
2 '''do''' <tex>color[u] \leftarrow</tex> WHITE
3 <tex>d[u] \leftarrow \mathcal {1}</tex>
4 <tex>p[u] \leftarrow</tex> NIL
5 <tex>color[s] \leftarrow</tex> GRAY
6 <tex>d[s] \leftarrow0</tex> 0
7 <tex>p[s] \leftarrow</tex> NIL
8 <tex>Q \leftarrow\varnothing</tex> Ø
9 ENQUEUE(<tex>Q</tex>, <tex>s</tex>)
10 '''while''' <tex>Q \ne \varnothing</tex>Ø
11 '''do''' <tex>u \leftarrow</tex> DEQUEUE(<tex>Q</tex>)
12 '''for''' (для) каждой <tex>м \in Adj[u]</tex>
