Обратите внимание на то, что функция main о запрашивает у вас как начальный город, так и город прибытия. Это значит, что вы можете использовать программу для поиска маршрута между любыми двумя городами. Но в этой главе предполагается, что Нью-Йорк- пункт отправления, а Лос-Анджелес - пункт прибытия или назначения. Если в программе заданы пункт отправления Нью-Йорк и пункт назначения Лос-Анджелес, на экран выводится следующее решение: сзяп? New York ? Los Angeles

ob.addflight( Chicago , Denver , 1000); ob.addflight( New York , Toronto , 500); ob.addflight( New York , Denver , 1800); ob.addflight( Toronto , Calgary , 1700); ob.addflight( Toronto , Los Angeles , 2500); 6b.addflight( Toronto , Chicago , 500); ob.addflight( Denver , Urbana , 1000); ob.addflight( Denver , Houston , 1000); ob.addflight( Houston , Los Angeles , 1500); db.addflight( Denver , Los Angeles , 1000);

Получает пункты отправления и назначения, cout From? ;

cin.getline(from, 40); cout To? ;

cin.getline(to, 40);

Проверяет, есть ли маршрут меязду from и to. ob. findroute(from, to);

Если маршрут существует, отображает его. if(ob.routefound()) ob.route();

return 0;

Пос-Анджелес

Лос-Анджелес

Рис. 7.7. Путь, ведущий к решению, полученный методом поиска в глубину

Как показывает функция maino, для использования класса search прежде всего создается объект типа search. Затем загружается база данных с прямыми рейсами между городами (соединениями). Далее вызывается функция findroute (), которая пытается найти маршрут между пунктами отправления и назначения. Для того чтобы проверить, найден ли такой маршрут, вызывается функция routefoundO. Она возвращает true, если он существует-Найденный путь отображается с помощью функции route (). Давайте подробно рассмотрим каждый фрагмент поиска в глубину.

New York to Chicago to Denver to Los Angeles Distance is 2900

Если вы посмотрите на рис. 7.7, то увидите, что это действительно первое решение, которое может быть найдено поиском в глубину. И это довольно хорошее решение.

функция matchO

функция match (), приведенная далее, определяет, есть ли рейс между двумя

Юродами, заданными в переменных from и to.

Если существует прямой рейс между from и to,

запоминает длину рейса в dist.

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

false - в противном случае.

bool Search::match(string from, string to, int &dist) {

for(unsigned i=0; i < flights.size(); i++) { if(flights[i].from == from &&

flights[i].to == to && !flights[i].skip)

flights[i].skip = true; препятствует повторному использованию dist = flights[i].distance; return true;

return false; не найден

Функция match о просматривает вектор flights в поисках любого элемента, у которого пункты отправления и назначения совпадают со значениями переменных from и to соответственно. Она возвращает false, если такого рейса не существует. Если такой рейс есть, функция возвращает true, в этом случае она также извлекает расстояние между городами и запоминает его в переменной, на которую ссылается ее параметр dist.

Обратите внимание на то, что функция match () игнорирует рейсы, у которых поле skip равно true. Если рейс найден, его полю skip присваивается значение true. Эти действия управляют возвратом из тупиков (dead ends), препятствуя многократной проверке одних и тех же рейсов.

Функция findO

функция findO, приведенная далее, исследует базу данных в поисках любого рейса из заданного в переменной from пункта отправления.

Для заданного from находит любой рейс. Возвращает true, если рейс найден, и false - в противном случае.