Олег Деревенец - Песни о Паскале

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

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

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

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

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

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

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

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

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

Здесь показаны лишь ребра, идущие от узла «H», но подобные списки содержатся и в других узлах. Например, в списке связей узла «G» есть ссылка на узел «H», поскольку узлы взаимно связаны. Так парами указателей создаётся двусторонняя связь узлов G и H (рис. 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».