Train 1.2 (19Dec2009) – Очередь(Поиск в ширину)

На прошлом занятии мы рассмотрели структуру данных Стек, а также одно из его применений на примере поиска в глубину. Сегодня обратим свое внимание в сторону такой структуры данных, как Очередь. Как и раньше на текущем этапе мы не будем разбирать внутреннюю реализацию очереди, а рассмотрим уже готовую STL-скую. Справочную информацию можно почитать здесь.

Одним из самых ярких применений очереди можно пронаблюдать на примере алгоритма Поиска в ширину (BFS).

Задача "Путешествие шахматного коня" (Поиск в ширину)
Технические моменты:
Для того, чтобы было удобно перебирать все соседние клетки, достижимые из текущей, шагом коня, предлагаю воспользоваться массивом движений:

1. int moveX[8] = {-2,-2,-1,-1,1,1,2,2};
2. int moveY[8] = {-1,1,-2,2,-2,2,-1,1};

Основная идея:
Рассмотрим работу поиска в ширину пошагово на основе тестового примера (A5 C2). Для более удобного представления шахматной доски в виде матрицы будет считать буквенную часть координаты номером строки, а числовую – номером столбца.
Условные обозначения:
1. Красным шрифтом выделена вершина очереди.
2. Синим шрифтом выделены клетки, достижимые из вершины очереди и не использованные ранее.
3. Желтым цветом подсвечены клетки находящиеся в очереди.
4. Черным шрифтом выделены клетки, которые уже отработаны.

       
        

Останавливаем работу нашей программы в тот момент, когда на текущем шаге конечная точка стала достижима.

Исходный код: Здесь

Задача "Разрезание листа" (Поиск в ширину)

Основная идея:
Вспомним идею решения этой же задачи с помощью поиска в глубину(ссылка) и просто заменим процедуру поиска достижимых вершин из текущей алгоритмом поиска в ширину.

Комментарии:
Алгоритмическая сложность DFS и BFS одинаковая O(N^2). Если переформулировать задачу на язык графов, то здесь нужно было найти количество компонент связности. В данной задаче не принципиально какой метод использовать. DFS пишется быстрее, в то время как BFS решает ту же задачу без рекурсии, экономя память. 
Если же рассматривать предыдущую задачу, где нужно было найти минимальное количество шагов до конечной клетки, то здесь нужно использовать только BFS(или другой специализированный алгоритм).
DFS дает ответ на вопрос: “Достижима ли вершина из текущей?”
BFS дает ответ на вопрос: “За какое минимальное количество шагов достижима вершина и текущей?”

Исходный код: Здесь