Текст книги "Песни о Паскале (СИ)"

Автор книги: Олег Деревенец

сообщить о нарушении

Текущая страница: 23 (всего у книги 29 страниц)

• Очереди и стеки, построенные на списках, могут хранить данные любых типов, при этом общий объём хранимых данных ограничивается лишь размером кучи.

• Не засоряйте кучу ненужными переменными, удаляйте их процедурой Dispose.

А слабо?

А) В Borland Pascal (только в нём) существует встроенная функция по имени MemAvail (от Memory – «память», Available – «доступный»). Функция возвращает свободный на текущий момент объём памяти в куче.

Если вы работаете в Borland Pascal, вставьте в процедуру Push и функцию Pop следующие операторы печати:

      Writeln(’Push :’, MemAvail);

и

      Writeln(’Pop :’, MemAvail);

Проследите таким образом за изменением объёма свободной памяти в куче.

Б) В главе 45 было высказано предположение, что для записи в танцевальный кружок достаточно одной очереди. Покажите это, создав соответствующую программу. Чем потребуется дополнить механизм работы с очередью?

Глава 57

Графомания

Я чуть не забыл о придворном программисте Нике! В 49-й главе он решил задачу о минимальной сумме пошлин. Тогда же купцы уговорили его взяться за программу для поиска кратчайшего маршрута между двумя странами. Купцы страдали от пошлин и хотели сократить свои расходы на границах. Ник принял заказ и впал в размышления.

На рис. 130 показан вид из космоса на континент, где проживал Ник. Тамошние страны именовались, как вы помните, латинскими буквами.

Рис.130 – Карта континента

Программа, что создал Ник в 38-й главе, превратила эту карту в следующий файл.

A B D F I

B A C I H

C B D

D A C E

E D F

F A E G

G H I F

H G I B

I A B G H

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

Данные были, только решение куда-то ускользало. Вот берег озера, где спрятался Ник. Его рука в который раз царапает на мокром песке одну и ту же картинку (рис. 131).

Рис.131 – Картинка на мокром песке

Здесь вместо разделяющих царства границ, Ник нацарапал соединяющие их дороги. «Вот по этим дорогам поедут купцы, – размышлял он, – но как именно?». Озарение явилось внезапно. «Постой-ка, мне знакома эта картинка! Неужто граф? Я что-то читал о них, надо бы вспомнить!». Оставим ненадолго озаренного Ника, и выясним, что это за штука такая – граф?

Видимое представление графа

Слово «граф» намекает на рисование, графику. Но программисты и математики признают графом не любую картинку. Граф для них – это сеть связанных между собой объектов. Объекты называют вершинами или узлами графа, а связи между ними – ребрами или дугами. В англоязычной литературе используют термины Node – узел, и Link – связь.

Вот знакомая картинка – схема московского метро (Рис. 132), это пример графа. Здесь станции являются узлами графа, а пути между ними – ребрами. Соседние узлы графа называют смежными. Кстати, нырнувший в метро пассажир решает ту же задачу, что и Ник: ищет кратчайший путь между двумя станциями.

Рис.132 – Схема московского метрополитена – это граф

А вот ещё примеры графов: карта автомобильных дорог, дерево родственных связей, электрическая схема. Вы можете придумать свои примеры. Или взять нацарапанный Ником рисунок, где узлами являются страны, а ребрами – дороги, их соединяющие.

Мы рассмотрели внешнее, видимое представлении графа, теперь обратимся к его внутреннему представлению в памяти компьютера.

Внутреннее представление графа

С внутренним представлением графа вы отчасти знакомы. Не удивляйтесь, ведь односвязный список – это тоже граф. Элементы списка – это узлы графа, а связи между элементами – это ребра. И хотя связь между узлами списка однонаправленная, такие графы тоже имеют право на жизнь. Разве нет дорог с односторонним движением?

Рис. 133 – Односвязный список – это разновидность графа

Годится ли такой список для представления графа, нацарапанного Ником? Рисунок на песке очевидно сложнее списка, – в нём много связей между узлами. К тому же связи на схеме Ника двунаправленные, ведь по дорогам можно ехать в обе стороны. Для представления такого графа требуется что-то похитрее списка. Но в этой замысловатой конструкции найдется место и односвязным спискам.

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

Теперь о связях. Очевидно, что их представим указателями. Но сколько их потребуется? Ведь из разных узлов исходит разное количество связей (рис. 131). Я предлагаю поместить в каждом узле список его связей с соседями. Неслабый получается узелок – с собственным списком внутри! Устройство этого списка связей мы обсудим чуть позже.

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

Рис.134 – Организация связей графа на примере узла «H»

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

Видимые нам ребра графа формируются списками, что вставлены внутрь каждого узла. Головы этих списков – это поля mLink. Чтобы не загромождать схему, я показал лишь список для узла «H». Элементы списка связей вытянулись на схеме слева направо, они сцеплены полями mNext, – не путайте их с полями mNext в узлах графа. Полезной нагрузкой элементов списка связей будут указатели mNode, ссылающиеся на соседние узлы. Именно эти ссылки, показанные на схеме жирными стрелками, определяют видимую форму графа, то есть его ребра. На рис. 135 показана часть графа, соответствующая схеме рис. 134.

Рис.135 – Часть графа, соответствующая схеме рис. 134

Здесь показаны лишь ребра, идущие от узла «H», но подобные списки содержатся и в других узлах. Например, в списке связей узла «G» есть ссылка на узел «H», поскольку узлы взаимно связаны. Так парами указателей создаётся двусторонняя связь узлов G и H (рис. 136).

Рис.136 – Ребро графа (слева) и внутреннее его представление (справа)

Прежде, чем выразить эту мудреную структуру на Паскале, повторю основные идеи.

• Узлы графа представлены записями.

• Каждая запись узла содержит: 1) «полезные» поля, 2) голову списка ребер и 3) указатель на следующий узел во вспомогательном списке.

• Полезной нагрузкой в списке ребер являются указатели на смежные узлы графа.

Все кажется, запутано, словно паутина (а паутина – это тоже граф!). Однако выраженное на Паскале это описание выглядит не таким уж страшным.

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

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

      TLink = record       { Элемент списка связей }

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

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

      end;

      TNode = record       { Узел графа (страна) }

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

      mLinks: PLink; { список связей с соседями (ребра) }

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

      end;

var List : PNode; { список всех стран континента (узлов графа) }

Здесь определены два типа записей: элемент для списка узлов (TNode) и элемент для списка связей (TLink). Соответственно объявлены и два типа указателей на них. Для доступа к графу нужна всего одна глобальная переменная List – указатель на первый элемент во вспомогательном списке. И это все! Как видите, пока ничего сложного.

Ввод и вывод графа

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

Напомню ещё раз кусочек входного файла, с которым мы будем иметь дело.

A B D F I

B A C I H

C B D

Здесь первый символ строки – это имя страны, а последующие – её соседи. Например, в третьей строчке показано, что страна «C» соседствует со странами «B» и «D».

Сначала обсудим алгоритм ввода графа в общих чертах.

Разумеется, что файл будем обрабатывать построчно. Взяв первый символ строки, проверим, нет ли во вспомогательном списке узла с таким именем? Возможно, что узел для этой страны уже создан при обработке предыдущих строк (что будет ясно из следующего абзаца). Если узел ещё не создан, создаем его и вставляем во вспомогательный список (обозначим этот узел буквой P).

Далее просматриваем оставшиеся символы строки. Для каждого из них тоже проверяем наличие готового узла. Если его нет, создаем этот узел (назовем его q), вставляем во вспомогательный список, и устанавливаем связь между узлами P и q. Эта связь будет односторонней: от P к q. Но, поскольку связь для каждой пары узлов устанавливается дважды, то, в конце концов, мы получим двусторонние связи. Например, при обработке второй строки файла будет установлена связь «B» –> «C», а при обработке третьей – связь «B» <– «C».

Теперь всё сказанное изобразим блок-схемой (рис. 137).

Чтобы облегчить себе дальнейший труд, заготовим две функции и процедуру, а именно:

• функцию для поиска узла по его имени;

• функцию для создания нового узла;

• процедуру для установки связи между двумя узлами.

Функцию поиска узла по его имени объявим так:

function GetPtr(aName : char): PNode;

Она ищет во вспомогательном списке узел по заданному в параметре имени. В случае успеха, функция вернет указатель на узел, а иначе – NIL.

Функция MakeNode создает новый узел графа с заданным именем, вставляет его во вспомогательный список узлов и возвращает указатель на этот узел.

function MakeNode(aName : Char): PNode;

И, наконец, процедура установки связей Link добавляет в список связей первого узла элемент связи со вторым узлом.

procedure Link(p1, p2 : PNode);

Все три подпрограммы очень просты, поскольку работают со списками.

Рис.137 – Алгоритм чтения графа

Немногим сложнее будет процедура распечатки графа, она объявлена так:

procedure ExpoData(var F: Text);

Процедура пробегает по вспомогательному списку узлов и спискам связей, распечатывая имена стран и их соседей.

Остальные детали алгоритма пояснены в программе «P_57_1».

{ P_57_1 – Ввод и вывод графа }

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

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

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

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

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

      end;

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

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

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

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

      end;

var List : PNode; { список всех стран континента (узлов графа) }

      { Функция поиска страны (узла графа) по имени страны }

function GetPtr(aName : char): PNode;

var p : PNode;

begin

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

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

while Assigned(p) do begin

if p^.mName= aName

      then break       { нашли! }

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

end;

GetPtr:= p;

end;

{ Функция создает новую страну (узел), вставляет в глобальный список List

и возвращает указатель на новый узел }

function MakeNode(aName : Char): PNode;

var p : PNode;

begin

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

p^.mName:= aName; { копируем имя }

p^.mLinks:=nil; { список связей пока пуст }

p^.mNext:= List; { указатель на следующий берем из заголовка }

List:= p;       { заголовок указывает на новый узел }

MakeNode:= p;       { результат выполнения функции }

end;

      { Процедура установки связи узла p1 с узлом p2 }

procedure Link(p1, p2 : PNode);

var p : PLink;

begin

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

p^.mLink:= p2;       { поле mLink должно указывать на p2 }

p^.mNext:= p1^.mLinks; { указатель на следующий берем из заголовка }

p1^.mLinks:= p;       { заголовок указывает на новый узел }

end;

      { Процедура чтения графа из текстового файла }

procedure ReadData(var F: Text);

var C : Char;

p, q : PNode;

begin

Reset(F);

while not Eof(F) do begin

if not Eoln(F) then begin { если строка не пуста }

      Read(F, C);       { читаем имя страны }

      C:=UpCase(C);       { перевод в верхний регистр }

      p:= GetPtr(C);       { а может эта страна уже существует? }

      if not Assigned(p)

      then p:= MakeNode(C); { если нет, – создаем }

      while not Eoln(F) do begin { чтение стран-соседей до конца строки }

      Read(F, C);

      C:= UpCase(C);

      if C in ['A'..'Z'] then begin { если это имя страны, а не пробел }

      q:= GetPtr(C);       { проверяем существование страны }

      if not Assigned(q)       { если не существует, – создаем }

      then q:= MakeNode(C);

      Link(p, q);       { связываем страну p с q }

      end

      end

end;

Readln(F); { переход на следующую строку файла }

end;

Close(F);

end;

      { Процедура распечатки графа }

procedure ExpoData(var F: Text);

var p : PNode;

q : PLink;

begin

Rewrite(F);

p:= List; { начало просмотра списка стран (узлов) }

while Assigned(p) do begin

Write (F, p^.mName);       { название страны }

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

while Assigned(q) do begin

      Write(F, ' ', q^.mLink^.mName); { название соседа }

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

end;

Writeln(F);       { конец строки }

p:= p^.mNext; { следующая страна }

end;

Close(F);

end;

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

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

List:= nil;

Assign(F_In, 'P_57_1.in');

ReadData(F_In);       { читаем граф из входного файла }

Assign(F_Out,'P_57_1.out');

ExpoData(F_Out);       { печатаем в выходной файл }

end.

Запустив эту программу, я обнаружил на выходе такой результат:

G I H F

E F D

H I G B

C D B

I H G B A

F G E A

D E C A

B H I C A

A I F D B

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

Ознакомившись с графами, мы готовы теперь последовать за придворным программистом Ником. Так айда в следующую главу!

Итоги

• Граф – это структура, состоящая из узлов и соединяющих их ребер.

• В памяти компьютера граф можно представить списком узлов и списками связей.

• Двунаправленные ребра графа представляются парой указателей.

• Порядок перечисления узлов и связей графа не имеет значения, поскольку не влияет на форму графа.

А слабо?

А) Когда-то страны континента (рис. 130) не поддерживали дипломатических связей. Изобразите отвечающий этой эпохе граф, отражая ребрами дипломатические отношения. Кстати, такой граф без ребер называют лесом.

Б) В пору расцвета континента все страны установили между собой дипломатические отношения. Нарисуйте подобающий граф.

В) В период политического кризиса соседние страны перессорились между собой и разорвали дипломатические отношения. Какие ребра графа уцелели? Нарисуйте его.

Г) Пусть названия стран представляются не буквами, а словами. Возьмите карту Европы и создайте входной файл для нескольких соседних стран, например:

Франция Испания Италия Бельгия Швейцария

Италия Франция Швейцария Словения

и так далее, перечисляя страны-соседи и отделяя их одним или несколькими пробелами. Напишите программу для ввода и вывода такого графа. Что придется изменить в структуре узла?

Глава 58

По графу шагом марш!

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

Рис.138 – Возможные пути из «E» в «H»

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

Империя номер два

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

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

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

Рис.139 – Начало строительства империи из страны «E»

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

Рис.140 – Состояние империи после присоединения первой страны

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

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

Рис.141 – Состояние империи после присоединения страны «D»

Рис.142 – Состояние империи после присоединения страны «F»

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

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

Рис.143 – Порядок возврата в исходный узел «Е» по цепочке обратных связей

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

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

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

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

Рис.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» и увидел на экране вот что.