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

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

В приводимом описании процедуры поиска в ширину (BFS – Breadth First Search) a – стартовая вершина, Q – очередь открытых вершин.

Procedure BFS(a)

1 Посетить(a);

2 while do

3 ;

4 for do

5 if y новая then посетить(y);

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

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