Информацию об авиарейсах компании XYZ Airlines можно представить в виде ориентированного графа (рис. 25.3). Ориентированным графом (или орграфом) называется граф, в котором каждое ребро (линия, соединяющая вершины графа) рассматривается как направленное. На рисунке это направление движения по ребру, изображаемому линией, показывает стрелка. В этом графе по ребру нельзя двигаться в направлении, противоположном тому, которое показано его стрелкой.
| Страница №2 |
Чтобы дать иное, более понятное представление графа авиарейсов компании XYZ Airlines, его изобразили в виде дерева (рис. 25.4). Теперь этот вариант будет использоваться нами вплоть до конца главы. Цель, т.е. конечный пункт путешествия — Лос-Анджелес, — обведена кружком. Кроме того, обратите внимание, что для того чтобы граф было проще представить в виде дерева, некоторые города в нем показаны несколько раз.
Теперь можно приступить к разработке разных программ поиска, с помощью которых можно будет выбирать маршрут от Нью-Йорка до Лос-Анджелеса.
| Страница №3 |