Структура данных - первый обход ширины

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

Как и в примере, приведенном выше, алгоритм BFS переходит сначала от A к B, к E к F, затем к C и, наконец, к D. Он использует следующие правила.

• Правило 1 - Посетите соседнюю не посещенную вершину. Отметить как посещенный Покажите это. Вставьте его в очередь.

• Правило 2. Если соседняя вершина не найдена, удалите первую вершину из очереди.

• Правило 3 - Повторяйте Правило 1 и Правило 2, пока очередь не станет пустой.

шаг	пересечение	Описание
1		Инициализируйте очередь.
2		Мы начинаем с посещения S (начального узла) и помечаем его как посещенный.
3		Затем мы видим не посещенный соседний узел из S. В этом примере у нас есть три узла, но в алфавитном порядке мы выбираем A , помечаем его как посещенный и ставим в очередь.
4		Далее, непосещенный соседний узел из S - это B. Мы помечаем его как посещенный и ставим в очередь.
5		Далее, непосещенный соседний узел из S - это C. Мы помечаем его как посещенный и ставим в очередь.
6		Теперь S осталось без невидимых соседних узлов. Итак, мы снимаем с очереди и находим A.
7		Из A мы имеем D как не посещаемый соседний узел. Мы помечаем его как посещенный и ставим в очередь.

На этом этапе у нас не осталось немаркированных (не посещенных) узлов. Но в соответствии с алгоритмом мы продолжаем отключение, чтобы получить все не посещенные узлы. Когда очередь очищается, программа заканчивается.

Реализацию этого алгоритма на языке C можно увидеть здесь .