Алгоритм поиска в ширину (BFS) перебирает график в движении по ширине и использует очередь для запоминания, чтобы получить следующую вершину для начала поиска, когда тупик возникает на любой итерации.
Как и в примере, приведенном выше, алгоритм BFS переходит сначала от A к B, к E к F, затем к C и G, наконец, к D. Он использует следующие правила.
-
Правило 1 — Посетите соседнюю не посещенную вершину. Отметить как посещенный Покажите это. Вставьте его в очередь.
-
Правило 2 — Если соседняя вершина не найдена, удалите первую вершину из очереди.
-
Правило 3 — Повторяйте Правило 1 и Правило 2, пока очередь не станет пустой.
Правило 1 — Посетите соседнюю не посещенную вершину. Отметить как посещенный Покажите это. Вставьте его в очередь.
Правило 2 — Если соседняя вершина не найдена, удалите первую вершину из очереди.
Правило 3 — Повторяйте Правило 1 и Правило 2, пока очередь не станет пустой.
| шаг | пересечение | Описание |
|---|---|---|
| 1 |  |
Инициализируйте очередь. |
| 2 |  |
Мы начинаем с посещения S (начальный узел) и помечаем его как посещенный. |
| 3 |  |
Затем мы видим не посещенный соседний узел из S. В этом примере у нас есть три узла, но в алфавитном порядке мы выбираем A , помечаем его как посещенный и ставим в очередь. |
| 4 |  |
Далее, непосещенный соседний узел из S — это B. Мы помечаем его как посещенный и ставим в очередь. |
| 5 |  |
Далее, непосещенный соседний узел из S является C. Мы помечаем его как посещенный и ставим в очередь. |
| 6 |  |
Теперь S осталось без невидимых соседних узлов. Итак, мы снимаем с очереди и находим A. |
| 7 |  |
Из A мы имеем D как не посещаемый соседний узел. Мы помечаем его как посещенный и ставим в очередь. |
На этом этапе у нас не осталось немаркированных (не посещенных) узлов. Но в соответствии с алгоритмом мы продолжаем отключение, чтобы получить все не посещенные узлы. Когда очередь очищается, программа заканчивается.
Реализацию этого алгоритма на языке C можно увидеть здесь .