Метод поиска в ширину

При поиске в ширину (breadth-first search) сначала анализируются все соседи текущей вершины. Затем – соседи соседей соседей и т.д. Пока процедура не рассмотрит все вершины, находящиеся на расстоянии n ребер от стартовой, перехода к более далеким вершинам, длина пути до которых (в ребрах) равна n+1, не произойдет.

Если упрощенно записать текст программы на псевдокоде, то он будет выглядеть следующим образом:

Эта процедура застрахована от «застревания». Даже если какая-то вершина попадет в список просматриваемых соседей вторично, все равно ее приоритет окажется более низким по сравнению с вершинами, уже находящимися там.

Проблема поиска в ширину (часто делающая его непригодным на практике) заключается в солидных затратах памяти. На каждом шаге процедура сохраняет в списке все вершины, находящиеся на некоторой «глубине» от стартовой. Если граф, к примеру, имеет вид бинарного дерева (очень частая ситуация на практике), количество хранимых вершин растет экспоненциально. На первом шаге нам понадобится держать в памяти лишь стартовую вершину, затем – ее двух потомков, затем – четыре вершины и т.д. Уже на десятом шаге размер списка составит 1024 элемента, а на двадцатом - 1048576 элементов. А ведь двадцать вершин «вглубь» - это, в принципе, не так много для процедуры просмотра (особенно если речь идет всего лишь о бинарном дереве, а не о более ветвистой структуре данных). Кроме того, приведена упрощенная реализация, которая только ищет целевую вершину, но не строит маршрута от стартовой вершины до нее. Если также строить маршрут, придется потратить даполнительную память.

Дата добавления: 2015-08-05