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

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

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

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

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

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

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

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

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