Песни о Паскале

Глава 58 По графу шагом марш!

Ознакомившись с графами, вернемся к программисту Нику, который все ещё царапает прибрежный песочек. «Если бы, – бормочет Ник, – мне надо было попасть из страны «E» в страну «H», то я бы поехал так». И он прочертил жирные стрелки, ведущие к цели через узлы «F» и «G» (рис. 138). «Но это я сообразил, глядя на карту, а без карты можно блуждать вот так», – и нацарапал стрелки, показанные пунктиром.

Как растолковать компьютеру верный путь? Нужна свежая идея! Новое – это всего лишь забытое старое – почему-то вспомнилось ему. «А не построить ли тебе здесь империю, как ты сделал это в 49-й главе?» – шепнул Нику внутренний голос. И мысли программиста двинулись в этом направлении.

Друзья, что вы слышали о постройке нынешних империй? Ведь на дворе не лютое средневековье! К чему проливать кровь, если от желающих нет отбоя, и очередь на присоединение к империям не пустует? Очередь упомянута мною не зря, – она играет важную роль в будущем алгоритме. Кстати, алгоритм этот придумали не программисты, а политики. Судите сами, сейчас вместе с Ником мы последуем их примеру.

На рис. 139 показан граф в начале строительства «империи» (дальше я пишу это слово без кавычек). Условимся об окраске его узлов. Все страны континента (узлы) отнесем к трем категориям: 1) независимые страны, 2) страны, желающие присоединиться к империи и 3) страны, вошедшие в её состав. Независимые страны окрасим белым цветом, желающие присоединиться – серым, а присоединенные к империи – черным.

Откуда начать строительство? Пусть центром империи будет страна «E». Окрасим её серым цветом и поставим в очередь на присоединение. Можно сказать, что страна «E» – первый кандидат на включение в несуществующую пока империю.

Серому кандидату поставим жесткое условие: хочешь быть принятым в империю и почернеть? Тогда уговори своих белых соседей тоже стать в очередь на присоединение и перекраситься в серый цвет. Так, страну «E» примут в империю, когда кандидатами на присоединение станут царства «D» и «F», что и показано на рис. 140. Кандидат, выполнивший это условие, удаляется из очереди на присоединение и включается в империю – чернеет.

К слову сказать, строя империю, Ник постоянно думал о купцах. Жирными стрелками на графе он помечал их воображаемое движение, как если бы купцы шли вослед завоевателям.

Итак, страна «E» вошла в империю, а два её соседа – «D» и «F» – стали в очередь на присоединение (в каком именно порядке – «D», затем «F» или наоборот – неважно). От них требуют то же самое – уговорить своих белых соседей. Так, для присоединения страны «D» ей надо убедить стать в очередь страны «A» и «C». По мере выполнения этого условия страны-кандидаты чернеют и удаляются из очереди. После двух следующих присоединений (стран «D» и «F») граф и очередь изменятся так, как показано на рис. 141 и рис. 142. Здесь же стрелками показано и воображаемое продвижение купцов.

Итак, строительство двинулось, но когда оно закончится? Очевидно, что страны с окраин империи рано или поздно войдут в число желающих, то есть, станут серыми, и тогда не останется белых соседей. А раз так, то очередь на присоединение постепенно опустеет, все страны почернеют, и строительство империи прекратится.

«Хорошо, – скажете, – только, причем тут поиск кратчайшего пути?». Но мы ведь не зря пустили купцов вослед завоевателям! Если купец потянет за собой ниточку, исходящую из начального узла «E», то из любого узла империи сможет вернуться к началу, следуя по нити в обратном направлении (Рис. 143).

Ник догадался, что путь из любого узла графа вдоль этих ниточек к исходной точке будет кратчайшим. Это следует из того, что империя расширялась присоединением ближайших соседей. Действительно, узлы «D» и «F» – ближайшие к исходному узлу «E», ведь они его соседи. Точно так же узел «G» – ближайший к узлу «F», а узел «H» – ближайший к узлу «G». Эти рассуждения справедливы для любых ниточек обратных связей.

Цепочки обратных связей тоже образуют граф, называемый деревом. Программисты часто применяют деревья, основное свойство которых состоит в наличии единственного пути между любыми узлами. Узел, из которого начато строительство дерева, является его корнем – это центр построенной нами империи (не географический, а политический центр).

Итак, строительство империи породило дерево обратных связей. Но как организовать эти ниточки? Введем в структуру узла ещё одно поле – указатель на узел, из которого мы пришли сюда по ходу расширения империи. Назовем это поле mPrev – предыдущий. Например, для узлов «F» и «D» предыдущим будет узел «E».

Остроумный Ник додумался по ходу строительства империи убить ещё одного зайца: определить длину пути от любого узла до центра. Так одновременно решается задача о минимальном количестве пересекаемых границ, которую в 49-й главе он решал через массив множеств. В самом деле, к чему плодить две программы, если можно обойтись одной? Ведь в ходе постройки дерева обратных связей определить расстояния несложно. Достаточно при переходе к очередному узлу отмечать в нём расстояние к центру империи, – оно будет на единицу больше того, что хранится в предыдущем узле. В центре империи это расстояние равно нулю, а в остальных узлах будет таким, как показано на рис. 144.

Подведем итог размышлениям Ника. Для поиска кратчайшего пути между двумя узлами графа, а заодно и определения расстояния между ними, сначала построим империю, центром которой будет один из этих двух узлов. Алгоритм этот называют обходом графа в ширину, он служит основой для решения многих задач на графах. Обход графа – не пустая прогулка. Двигаясь по нему, мы разместим в узлах информацию, необходимую для второго этапа решения – формирования кратчайшего пути.

Теперь уточним полезную нагрузку узла, что добавится в него? Во-первых, это упомянутый выше указатель на предыдущий узел mPrev – ниточка обратной связи. Во-вторых, надо застолбить поле для расстояния к центру империи, назовем его mDist – «дистанция». Не забыть бы поле для окраски узла одним из трех цветов: белым, серым или черным. Назовем это поле mColor – «цвет», и будем хранить в нём одно из перечислимых значений цвета: White, Gray, Black (о перечислениях сказано в главе 32). В итоге проясняется следующая структура для узла графа:

type TColor = (White, Gray, Black); { Перечисление: белый, серый, черный }

    TNode = record     { Запись для страны (узел графа) }

    mName : Char; { Название страны (одна буква) }

    mColor: TColor; { цвет узла, изначально белый }

    mDist : integer; { длина пути к узлу, изначально -1 }

    mPrev : PNode; { узел, из которого пришли в текущий }

    mLinks: PLink; { список смежных узлов (ребер) }

    mNext : PNode; { связь во вспомогательном списке }

    end;

Приступаем к постройке империи. Эта версия программы пока не найдет кратчайших путей между узлами, но подготовит почву для этого. Мы пройдем по всем узлам графа в ширину, начиная с исходного узла – центра империи. И по ходу движения разместим в этих узлах нужную информацию – обратные ссылки и расстояния к центру империи.

Программу «P_58_1» построим на основе программы «P_57_1», – из неё возьмем процедуру ввода графа и добавим ещё несколько подпрограмм. Две из них нужны для очереди, элементами которой будут узлы графа.

procedure PutInQue(arg: PNode);

function GetFromQue(var arg: Pnode): boolean;

Впрочем, для вас эти подпрограммы тоже не новы, – вспомните запись в танцевальный кружок в программе «P_56_2». Там похожие процедуры применялись для очереди строк, а здесь организуется очередь узлов.

В начальный момент все вершины графа надо окрасить белым, – об этом позаботится простенькая процедура InitList. По-настоящему новой будет лишь процедура постройки империи Expand, вот её объявление.

procedure Expand(arg : PNode);

Она расширяет империю, начиная с заданного параметром arg узла. Алгоритм процедуры отвечает рассуждениям Ника, рассмотрим её подробней.

Перед входом в цикл заполняем поля стартового узла: в поле расстояния mDist заносим ноль, красим узел в серый цвет и ставим в очередь на присоединение. Теперь очередь содержит один элемент – исходный узел, то есть, центр империи.

Далее следует цикл WHILE, он выполняется, пока очередь желающих войти в империю не опустеет. Выбрав из очереди функцией GetFromQue первый узел (в этот момент очередь опустеет, но ненадолго), пробегаем по списку его белых соседей, располагая там нужную информацию, перекрашивая соседей в серый цвет и помещая их в очередь. После этого извлеченный из очереди узел P очерняем и возвращаемся к началу цикла WHILE. Поскольку очередь узлов уже не пуста (добавились соседние узлы), функция GetFromQue выберет из неё следующий узел, и цикл WHILE выполнится вновь. В конце концов белые узлы когда-то иссякнут. Тогда пополнение очереди прекратится, серые узлы постепенно будут выбраны из неё, очередь опустеет, и цикл WHILE завершится.

Вот, собственно и все. Для наблюдения за экспансией империи в процедуру вставлены операторы печати, не влияющие на её работу (они выделены).

{ P_58_1 – Обход графа в ширину }

type PNode = ^TNode; { Указатель на запись-узел }

    PLink = ^TLink; { Указатель на список связей }

    TColor = (White, Gray, Black); { Перечисление для цветов узла }

    TLink = record     { Список связей }

    mLink : PNode; { указатель на смежный узел }

    mNext : PLink; { указатель на следующую запись в списке }

    end;

    TNode = record     { Запись для хранения страны (узел графа) }

    mName : Char; { Название страны (одна буква) }

    mColor: TColor; { цвет узла, изначально белый }

mDist : integer; { длина пути к узлу, изначально -1 }

    mPrev : PNode; { узел, из которого пришли в данный }

    mLinks: PLink; { список смежных узлов (указатели на соседей ) }

    mNext : PNode; { указатель на следующую запись в списке }

    end;

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);

var p: PLink;

begin

New(p);     { создаем новую переменную-связь }

p^.mLink:= arg; { размещаем указатель на узел }

{ размещаем указатель в голове очереди }

p^.mNext:= Que; { указатель на предыдущую запись }

Que:=p;     { текущая запись в голове очереди }

end;

    { Извлечение из очереди указателя на узел }

function GetFromQue(var arg: Pnode): boolean;

var p, q: PLink;

begin

GetFromQue:= Assigned(Que);

if Assigned(Que) then begin

{ Поиск последнего элемента (хвоста) очереди }

p:= Que; q:=p;

{ если в очереди только один элемент, цикл не выполнится ни разу! }

while Assigned(p^.mNext) do begin

    q:=p;     { текущий }

    p:=p^.mNext; { следующий }

end;

{ p и q указывают на последний и предпоследний элементы }

arg:= p^.mLink;

if p=q     { если в очереди был один элемент… }

    then Que:= nil     { очередь стала пустой }

    else q^.mNext:= nil; { а иначе "отцепляем" последний элемент }

Dispose(p);     { освобождаем память последнего элемента }

end;

end;

{ Процедура расширения (экспансии) "империи", начиная с заданного узла arg }

procedure Expand(arg : PNode);

var p : PNode;

q : PLink;

begin

arg^.mDist:= 0;     { расстояние до центра империи = 0 }

arg^.mColor:= Gray;     { метим серым цветом }

PutInQue(arg);     { и помещаем в очередь обработки }

while GetFromQue(p) do begin { извлекаем очередной узел }

Write(p^.mName, ' ->');     { печатаем название узла – для отладки }

q:= p^.mLinks;     { начинаем просмотр соседей }

while Assigned(q) do begin

    if q^.mLink^.mColor = White then begin { если сосед ещё белый }

    q^.mLink^.mColor:= Gray;     { метим его серым }

    q^.mLink^.mDist:= p^.mDist +1; { расстояние до центра }

    q^.mLink^.mPrev:= p;     { метим, откуда пришли }

    PutInQue(q^.mLink);     { и помещаем в очередь обработки }

    Write(q^.mLink^.mName:2);     { имя соседа – это для отладки }

    end;

    q:= q^.mNext; { переход к следующему соседу }

end;

p^.mColor:= Black; { после обработки узла метим его черным }

Writeln;     { новая строка – это для отладки }

end;

end;

    { Инициализация списка узлов перед "постройкой империи" }

procedure InitList;

var p : PNode;

begin

p:= List; { начинаем с головы списка узлов }

{ проходим по всем элементам списка }

while Assigned(p) do begin

p^.mColor:= White; { цвет узла изначально белый }

p^.mDist := -1; { длина пути к узлу изначально -1 }

p^.mPrev := nil; { узел, из которого пришли в данный }

p:= p^.mNext;     { следующий узел }

end;

end;

var F_In {, F_Out} : Text; { входной и выходной файла }

    C : Char;     { название страны }

    Start : PNode; { узел, с которого начинается расширение "империи" }

begin {--- Главная программа ---}

{ Инициализация списка узлов и очереди узлов }

List:= nil; Que:= nil;

Assign(F_In, 'P_57_1.in');

ReadData(F_In);     { чтение графа }

{ Цикл ввода названий стран }

repeat

Write('Центр империи = '); Readln(C);

C:= UpCase(C);

if not (C in ['A'..'Z']) then break;

Start:= GetPtr(C);     { указатель на центр империи }

if Assigned(Start) then begin { если такая страна существует, }

    InitList;     { устанавливаем начальные значения в полях узлов }

    Expand(Start); { расширяем "империю" от центра Start }

end;

until false

end.

В главной программе организован цикл, принимающий от пользователя исходную страну, из которой строится империя. Программа завершается при вводе любого символа, отличного от латинской буквы. Запустив программу, я ввел символ «E» и увидел на экране вот что.

E -> F D

F -> G A

D -> C

G -> I H

A -> B

C ->

I ->

H ->

B –>

Эти строки напечатаны операторами трассировки в процедуре Expand. Согласно первой строке из узла «E» мы попадаем в узлы «F» и «D». Согласно второй – из узла «F» движемся в узлы «G» и «A», и так далее. Последние четыре строки показывают, что узлы «C», «I», «H» и «B» оказались на окраинах империи, и продвижений оттуда нет. По этой трассировке нетрудно нарисовать дерево воображаемого продвижения купцов (рис. 145).

Сопоставьте это дерево с тем, что нацарапал на песке придворный программист (рис. 144). Разницы не заметит только слепой. В чем дело? Неужели вкралась ошибка?

Но, прежде чем огорчаться, сравните расстояния между центром империи и другими узлами – на обоих рисунках они совпадают. А это значит, что можно найти разные варианты кратчайших путей. Какой из них выберет программа – дело случая. Точнее, это определяется порядком ввода узлов. Мы знаем, что порядок строк входного файла не влияет на форму графа, но он влияет на выбор одного из кратчайших путей между узлами. Правда, купцам до этого дела нет, – ведь расстояния по таким путям будут одинаковыми.

Теперь все готово для создания полной версии программы. Пройдясь по графу вширь, мы разместили в узлах необходимые данные: расстояния от корня и обратные ссылки на пройденные узлы. Пора ставить победную точку – напечатать кратчайший путь между двумя узлами и длину этого пути.

Для постройки кратчайшего пути надо указать узел, из которого мы хотим попасть в центр империи. Двигаясь из него по цепочке обратных ссылок в направлении центра, мы, в конце концов, попадем в него. Значение обратной ссылки в центре империи равно NIL, что будет признаком окончания пути. С этой работой справится несложная функция MakePath – «создать путь».

function MakePath(arg : PNode): string;

В функцию передается узел, от которого надо вернуться к корню дерева, то есть к центру империи. Результатом будет строка пути вида «A –> B –> C».

Главную программу слегка дополним. Теперь пользователь введет названия двух стран, между которыми ищется кратчайший путь: «откуда» и «куда». Страну «откуда» назначим центром империи, а из страны «куда» будем возвращаться по цепочке обратных ссылок, – она составит параметр функции MakePath. Поскольку вводятся названия стран, а не указатели на них, преобразование имен в указатели тоже сделаем в главной программе.

Итак, в главной программе выполняются:

• ввод графа из текстового файла;

• ввод имен двух стран и преобразование их в указатели;

• подготовка узлов графа – заполнение полей начальными значениями;

• обход графа в ширину из заданного корня;

• распечатка кратчайшего пути по цепочке обратных ссылок.

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

З) Напишите программу для определения страны, где можно провести съезд с наименьшими издержками (см. задачу Ж).

И) Решите задачи Ж и З для случая разной стоимости виз на границах.