Итак, в главной программе выполняются:
• ввод графа из текстового файла;
• ввод имен двух стран и преобразование их в указатели;
• подготовка узлов графа – заполнение полей начальными значениями;
• обход графа в ширину из заданного корня;
• распечатка кратчайшего пути по цепочке обратных ссылок.
Все действия, кроме первого, зациклим, – тогда пользователь сможет задавать для этого графа разные сочетания стран. Признаком выхода из цикла будет ввод любого символа, отличного от латинской буквы. Надеюсь, что сказанного достаточно, чтобы разобраться в программе «P_58_2». Эта программа включает части программ «P_57_1» и «P_58_1», которые я лишь обозначил.
{ P_58_2 – Поиск кратчайшего пути и определение расстояний в графе }
type { Описания типов взять из P_58_1 }
var List : PNode; { список всех стран континента }
Que : PLink; { очередь присоединяемых узлов }
{ Функция поиска страны (узла графа) по имени страны }
function GetPtr(aName : char): PNode;
{ Взять из P_57_1 }
end;
{ Функция создает новую страну (узел) }
function MakeNode(aName : Char): PNode;
{ Взять из P_57_1 }
end;
{ Процедура установки связи узла p1 с узлом p2 }
procedure Link(p1, p2 : PNode);
{ Взять из P_57_1 }
end;
{ Процедура чтения графа из текстового файла }
procedure ReadData(var F: Text);
{ Взять из P_57_1 }
end;
{ Помещение указателя на узел в глобальную очередь Que }
procedure PutInQue(arg: PNode);
{ Взять из P_58_1 }
end;
{ Извлечение из очереди указателя на узел }
function GetFromQue(var arg: Pnode): boolean;
{ Взять из P_58_1 }
end;
{ Инициализация списка узлов перед "постройкой империи" }
procedure InitList;
{ Взять из P_58_1 }
end;
{ Процедура расширения (экспансии) "империи", начиная с заданного узла arg }
procedure Expand(arg : PNode);
{ Взять из P_58_1,
выделенные там операторы для трассировочной распечатки удалить }
end;
{ Функция для формирования пути от центра империи к заданному узлу }
function MakePath(arg : PNode): string;
var p : PNode;
S : string;
begin
S:= arg^.mName; { имя конечного узла }
p:= arg^.mPrev; { указатель на предыдущий узел }
while Assigned(p) do begin { пока не достигли корня }
S:= p^.mName +' -> '+ S; { добавляем к пути имя узла }
p:= p^.mPrev; { переход к следующему узлу }
end;
MakePath:= S;
end;
var F_In {, F_Out} : Text; { входной и выходной файла }
C1, C2 : Char; { названия стран "откуда" и "куда" }
Start, Stop : PNode; { узлы "откуда" и "куда" }
begin {--- Главная программа ---}
{ Инициализация списка узлов и очереди узлов }
List:= nil; Que:= nil;
Assign(F_In, 'P_57_1.in');
ReadData(F_In); { чтение графа }
{ Цикл ввода названий стран }
repeat
Write('Откуда= '); Readln(C1);
C1:= UpCase(C1);
if not (C1 in ['A'..'Z']) then break;
Write('Куда = '); Readln(C2);
C2:= UpCase(C2);
if not (C2 in ['A'..'Z']) then break;
Start:= GetPtr(C1); { начальный узел }
Stop:= GetPtr(C2); { конечный узел }
if Assigned(Start) and Assigned(Stop) then begin
{ если такие страны существуют, }
InitList; { устанавливаем начальные значения в полях узлов }
Expand(Start); { расширяем "империю" от узла Start }
Writeln (Stop^.mDist:3, ’’:3, MakePath(Stop));
end;
until false
end.
И вот настал час испытаний, вводим данные и получаем это:
Откуда: E
Куда: H
3 E -> F -> G -> H
Ура! Заработало! Сколько труда за этой короткой строчкой! Оправданы ли наши усилия? Конечно! Истина дорого даётся, но теперь мы не заблудимся даже в многотысячном графе!
Графы — это мощный инструмент для решения широкого круга инженерных задач. Их применяют при сортировке и поиске данных (здесь используют деревья), в расчетах электрических схем и потоков жидкостей, — всё не перечислить. Мы отщипнули лишь краешек этого каравая, вы можете узнать о графах больше по книгам [9] и [17] из списка рекомендуемой литературы.
Итоги• Обход графа в ширину – это один из базовых алгоритмов обработки графов. На нём основано решение многих задач, в том числе – поиск кратчайшего пути между узлами.
• При решении задач на графах в его узлах размещают информацию, нужную для решения данной задачи. Иногда такую информацию размещают и в ребрах, для этого в структуру ребер вводят необходимые поля.
А слабо?А) Изобразите граф, содержащий не менее 20 вершин, обозначьте вершины латинскими буквами и поищите в этом графе кратчайшие пути программой «P_58_2».
Б) Пусть узлы графа – это города, а ребра – дороги между ними. Расстояния между городами разные и они известны. Как отразить в структуре графа эти расстояния? Предложите что-нибудь.
В) Пусть расстояния между городами указаны в поле mDist записи TLink.
TLink = record { Тип список связей }
mLink : PNode; { указатель на смежный узел }
mDist : integer; { расстояние между городами }
mNext : PLink; { указатель на следующую запись в списке }
end;
Предложите формат входного файла, содержащего в числе прочего расстояния между городами.
Г) Пусть выбран следующий формат входного файла, содержащий расстояния между городами (приведена одна строка).
A C 20 E 40
Здесь первый символ, как и ранее, обозначает текущий узел. Затем перечисляются его соседи с указанием расстояний до них. Например, между узлами «A» и «C» 20 км, а между узлами «A» и «E» – 40 км. Напишите процедуру ввода графа из такого файла.
Д) Напишите программу для поиска кратчайшего пути с учетом расстояний между городами. Подсказка: измените процедуру обхода в ширину так, чтобы серый кандидат исследовал всех соседей (не только белых), проверяя в них поле расстояния mDist. Если путь к соседу через кандидата окажется короче того, что уже отмечен в соседе, то следует изменить как расстояние, так и обратную ссылку в соседе. Вдобавок если сосед не серый, он ставится в очередь.
Е) Предположим, что купцам интересны не расстояния между столицами, а размер пошлин, вносимых при пересечении границ. Эти пошлины зависят от пересекаемой границы (то есть от пары стран). Годится ли для этого случая рассмотренная выше модель с разными расстояниями между городами?