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