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

и

Writeln(’Pop :’, MemAvail);

Проследите таким образом за изменением объёма свободной памяти в куче.

Б) В главе 45 было высказано предположение, что для записи в танцевальный кружок достаточно одной очереди. Покажите это, создав соответствующую программу. Чем потребуется дополнить механизм работы с очередью?

Я чуть не забыл о придворном программисте Нике! В 49-й главе он решил задачу о минимальной сумме пошлин. Тогда же купцы уговорили его взяться за программу для поиска кратчайшего маршрута между двумя странами. Купцы страдали от пошлин и хотели сократить свои расходы на границах. Ник принял заказ и впал в размышления.

На рис. 130 показан вид из космоса на континент, где проживал Ник. Тамошние страны именовались, как вы помните, латинскими буквами.

Программа, что создал Ник в 38-й главе, превратила эту карту в следующий файл.

A B D F I

B A C I H

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).

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

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

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

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

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

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

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