Структура данных - первый обход ширины
Алгоритм поиска в ширину (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 можно увидеть здесь .