Поиск в глубину

fJoucK в глубину (depth-first search) проверяет каждый возможный путь цели- ом, прежде чем перейти к другому возможному маршруту. Для того чтобы донять, как работает этот метод поиска, рассмотрим дерево, приведенное на РИс. 7.6. Узел F - цель поиска.

РИ поиске в глубину порядок обхода узлов графа - ABDBEBACF. Те, кто Знаком с деревьями, узнают в поиске в глубину метод, именуемый симметричным обходом дерева (inorder tree traversal). При обходе каждый раз выби-

контейнер библиотеки STL, который реализует динамический массив), рторая переменная - стек, названный btstack и используемый для возврата или отката. Как вы увидите, стек для возврата очень важен во всех вариантах поиска.

jacc Search содержит две встроенные функции: addfiighto и routefound (). Когда создается первый объект типа search, его вектор flights пуст. Рейсы между городами добавляются с помощью повторяющихся вызовов функции addfiighto с указанием пунктов отправления и прибытия, а также расстояния между ними. Функция addfiighto просто помешает каждый рейс в конец вектора flights, длина которого автоматически увеличивается для того, чтобы вместить новые данные, функция routefoundo определяет, существует ли маршрут между пунктами отравления и назначения, используя данные стека возврата. Если стек пуст, то между городами маршрута нет. В противном случае стек возврата содержит найденный маршрут (процесс формирования маршрута у разных способов поиска различный).

Реализация остальных членов класса search описана в следующих разделах. В табл. 7.3 приведено их краткое назначение.

рается левая ветвь, пока не достигнут конечный узел или не найдена цель Если текущий узел - конечный, совершается подъем на один уровень .вверх и выбирается правая ветвь дерева, а из нее продолжается движение по ле-вым ветвям до тех пор, пока не встретилась цель или конечный узел. Эта процедура повторяется, пока не обнаружена цель или не пройден последний узел пространства поиска.

( D , Е ; F G

Рис. 7.6. Дерево, использующееся при описании способа поиска в глубину

Как видите, поиск в глубину гарантирует обнаружение цели, в худшем случае он может выродиться в исчерпывающий поиск. В нашем примере исчерпывающий поиск будет проведен, если целью окажется узел G. В листинге 7.1 приведена полностью программа, выполняющая поиск в глубину.

Листинг 7.1. Реализация поиска в глубину

Поиск маршрута. #include <iostreain> #include <stack> #include <string> #include <vector>

using namespace std;

Информация о рейсе, struct Flightlnfo {

string from; пункт отправления

string to; пункт назначения

int distance; расстояние от и до...

tX3ol skip; используется при возврате или откате (бектрекинге)

FlightlnfoO { from = ; to = ; distance = 0; skip = false;

Flightlnfo(string f. string t, int d) { from = f; to = t; distance = d; skip = false;

Поиск маршрутов между городами с помощью поиска в глубину, class Search {

Этот вектор содержит информацию о рейсах.

vector<FlightInfo> flights;

Этот стек используется для возврата. stack<FlightInfo> btStack;

Если есть рейс от from и до to,

то в dist запоминается расстояние.

Возвращает true, если рейс существует, и

false - в противном случае, bool match (string from, string to, int &dist);

При заданном from ищет любой прямой рейс (соединение). Возвращает true, если рейс найден, и false - в противном случае, ool find(string from, Flightlnfo &f);