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

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