57
Заочная школа программирования
Урок 14: Работа с графами
На страницах «Кванта» за последние годы много раз публикались статьи о графах и связанных с ними математических задачах. Почти в каждой статье говорилось, что для решения таких задач широко использовался вычислительный машин. Сегодня мы расказываем о том, как работать с графами на ЭВМ, используя возможности языка Рапира.
Учащиеся ЗШП, не знакомые с основными определениями теории графов, могут их прочитать в статье В. Евстигнеева на с. 18 этого номера*).
*) Для выполнения заданий 14-го урока нет необходимости читать всю указанную статью: нужны только основные определения, данные в начале. Однако мы очень советем учащему ЗШП прочитать и подробно разобрать статью петликом.
Наруженные графы
Структура самых разнообразных систем, с которых приходит именно дело на практике, может быть описана при помощи графов. Очень часто встречаются задачи, в условиях которых нужно учитывать не только наличие связей между элементами системы, но и свойства этих связей, а также свойства самих элементов. Для описания условий таких задач приходит «нагружать» графы, то есть ставить в соответствии их ребрам или вершинам (а иногда и тем, и другим) какие-то числа, тексты или другие объекты. Например, если система дорог Шпаговского сельсовета (рис. 1, а) нужно представить в виде графа и не потребять при этом информации о длине каждой дороги, то получится граф с нагуженными ребрами (рис. 1, б).
Задание 14.1. Изобразите в виде нагуженного графа схему аваалиний между столцами соизных ресурвлик СССР с указанием расстояний.
Графы в памяти ЭВМ
Если в ходе решения задачи вам понадобится записать в памяти ЭВМ несколько множества и выполнить над ними общные математические опера-
в город Видеотон
пос. Робик
дер. Малая Бзсмовка
пос. Квант
Терминальная роза
с. Большие Шпади
дер. Крудые Сκόки
р. Информационный поток
Рис. 1.
58
Рис. 2.
рацини, то на языке Рапира вы суммеете это сделать без труда. Но специальных средств для работы с графами на Рапире нет, поэтому способ описания графа на этом языке программирования нужно придумать самим.
Посмотрим, что должно помнить машина, чтобы знать об ориентированном графе все, что нужно для решения задач. Во-первых, она должна помнить множество вершин. Для этого, конечно, нужно как-то обозначить каждую вершину, например, занумеровать, как на рисунке 2. Вовторых, необходимо помнить, где начинается и где заканчивается каждой дуга. Чаще всегодугу описывают при помощи кортежа, составленного из обозначений ее начальной и конечной вершин. Например, на том же рисункедугу, связывающий вершины 1 и 5, можно описать кортежем〈1,5〉.
Информацию о всехдугах орграфа можно запомнить в виде множества, составленного из таких кортежей. Наконец, кортеж, составленный из двух описанных множества — множества вершин и множества дуг, — это и есть полное описание орграфа на Рапире. Например, орграф, изображенный на рисунке 2, может быть описан так:
«1,2,3,4,5,6,7»
«1,3», «1,5», «1,4», «2,1»
«2,3», «3,5», «5,3», «5,6»
«5,7», «6,5», «6,6», «7,1»〉.
Задание 14.2. Нарисуйте ориентированный граф, описание которого на Рапире выглядит так:
«1,2,3,4,5,6», «1,4», «2,1»
«3,1», «3,2», «3,4», «3,5», «4,5»
«5,6», «6,2», «6,3»〉.
Если нужно описать орграф с нагруженными дугами, то в кортежах, описывающих дуги, появляется третий элемент — значение нагрузки. Задание 14.3. Граф БУКОВКИ описан на Рапире так:
«1,2,3,4,5,6»
«1,2’,T’», «2,3’,P’», «2,5’K’», «3,5’,A’»
«4,1’,H’», «4,4’,T’», «5,6’,B’», «6,4’,A’»〉
->БУКОВКИ;
Нарузкой каждой дуги является текст. Двiazаясь вдоль любого пути в графе и выписывая подряд соответствующие дугам тексты, можно получить различные слова.
a) Какой текст соответствует пути, проходящему через вершины 2,5,6,4,1,2?
b) По какому пути нужно выделяться, чтобы получилось слов ВАТА?
b) Существует ли в графе пути, двiazаясь вдоль которого можно было бы получить слов РАК? Слово ТРАВА?
Для того чтобы облегчить ввод сведений о графе в память ЭВМ, удобно описать функцию, которая будет запрашивать в диалоговом режиме все нужные сведения. Для ориентированного графа с занумерованным вершинами и дугами с числовой нагрузкой эта функция могла бы выглядеть так:
ПРОЦ ЗАПРОС = >ГРАФ;
«» ->ВЕРШИНЫ;«» ->ДУГИ;
ПЕЧАТЬ(‘СКОЛЬКО ВЕРШИН В ГРАФЕ?’);
ВВОД(1) ->ЧИСВЕР;1 ->НОМВЕР;
ПОКА НОМВЕР = <ЧИСВЕР::
ВЕРШИНЫ + «НОМВЕР»
->ВЕРШИНЫ;
НОМВЕР +1 ->НОМВЕР
ВСЕ;
‘ДА’ ->ПРОДОЛЖЕНИЕ;
ПОКА ПРОДОЛЖЕНИЕ = ‘ДА’::
ПЕЧАТЬ(‘НАЗОВИТЕ НАЧАЛЬНУЮ ВЕРШИНУ’);
ВВОД(1) ->НАЧВЕР;
ПЕЧАТЬ(‘НАЗОВИТЕ КОНЕЧНУЮ ВЕРШИНУ’);
ВВОД(1) ->НАГРУЗКА;
ЕСЛИ (НАЧВЕР ИЗ ВЕРШИНЫ)
И (КОНВЕР ИЗ ВЕРШИНЫ) TO ДУГИ + «НАЧВЕР,КОНВЕР, НАГРУЗКА» ->ДУГИ;
ПЕЧАТЬ(‘ЕСТЬ ЛИ ЕШЕ ДУГИ?’);
ВВОД(0) ->ПРОДОЛЖЕНИЕ