Олег Деревенец - Песни о Паскале

Все действия, кроме первого, зациклим, – тогда пользователь сможет задавать для этого графа разные сочетания стран. Признаком выхода из цикла будет ввод любого символа, отличного от латинской буквы. Надеюсь, что сказанного достаточно, чтобы разобраться в программе «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. Если путь к соседу через кандидата окажется короче того, что уже отмечен в соседе, то следует изменить как расстояние, так и обратную ссылку в соседе. Вдобавок если сосед не серый, он ставится в очередь.

Е) Предположим, что купцам интересны не расстояния между столицами, а размер пошлин, вносимых при пересечении границ. Эти пошлины зависят от пересекаемой границы (то есть от пары стран). Годится ли для этого случая рассмотренная выше модель с разными расстояниями между городами?

Ж) С некоторых пор купцы учредили свой ежегодный съезд – Континентальный Купеческий Конгресс, где обсуждали свои проблемы. Каждая страна отправляла на съезд по одному делегату, а расходы на пересечение границ (визы) оплачивались из общей кассы. Посчитайте эти расходы (1 пиастр за каждое пересечение), если известна страна проведения конгресса. Учтите, что купцы следовали на съезд кратчайшими маршрутами.