Песни о Паскале — страница 89 из 112

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 – Состояние империи после присоединения первой страны

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