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

В рассыпную!

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

Программу «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; { очередь присоединяемых узлов }