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

C B D
D A C E
E D F
F A E G
G H I F
H G I B
I A B G H

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

Данные были, только решение куда-то ускользало. Вот берег озера, где спрятался Ник. Его рука в который раз царапает на мокром песке одну и ту же картинку (рис. 131).

Рис.131 – Картинка на мокром песке

Здесь вместо разделяющих царства границ, Ник нацарапал соединяющие их дороги. «Вот по этим дорогам поедут купцы, – размышлял он, – но как именно?». Озарение явилось внезапно. «Постой-ка, мне знакома эта картинка! Неужто граф? Я что-то читал о них, надо бы вспомнить!». Оставим ненадолго озаренного Ника, и выясним, что это за штука такая – граф?

Видимое представление графа

Слово «граф» намекает на рисование, графику. Но программисты и математики признают графом не любую картинку. Граф для них – это сеть связанных между собой объектов. Объекты называют вершинами или узлами графа, а связи между ними – ребрами или дугами. В англоязычной литературе используют термины Node – узел, и Link – связь.

Вот знакомая картинка – схема московского метро (Рис. 132), это пример графа. Здесь станции являются узлами графа, а пути между ними – ребрами. Соседние узлы графа называют смежными. Кстати, нырнувший в метро пассажир решает ту же задачу, что и Ник: ищет кратчайший путь между двумя станциями.

Рис.132 – Схема московского метрополитена – это граф

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

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

Внутреннее представление графа

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

Рис. 133 – Односвязный список – это разновидность графа

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

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

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