Итак, страна «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; { очередь присоединяемых узлов }
{ Функция поиска страны (узла графа) по имени страны }