Поиск в ширину

При поиске в ширину порядок исследования дуг графа отличается. Поиск в ширину производится следующим образом:

1. Начинаем поиск с произвольной вершины r. Формируем множество текущих вершин A, включив в него вершину r.

2. Идем в ранее не пройденные вершины по всем дугам с начальной вершиной из множества A. Запоминаем эти дуги. Формируем множество A, включив в него конечные вершины пройденных дуг.

3. Процесс поиска (пункт 2) заканчивается, когда множество A станет пустым.

Поиск в ширину проиллюстрирован на рис. 3.17.