На этом шаге мы приведем общие сведения по реализации алгоритмов на графах.

При написании данного раздела были существенно использованы результаты изложенные в монографии [1, гл.4].

Знакомство со способами представления и обработки графов весьма поучительно. С одной стороны, графы являются достаточно наглядными объектами. С другой стороны, как мы скоро увидим, машинное представление графов допускает большое разнообразие. Сложность получения ответа на тот или иной вопрос относительно данного графа зависит, естественно, от способа представления графа. Поэтому в алгоритмах на графах взаимосвязь "алгоритм - структура данных" проявляется очень сильно. Один и тот же алгоритм, реализованный на различных структурах данных, часто приводит к совершенно разным программам. Этот факт позволит нам на относительно небольшом числе алгоритмов проиллюстрировать широкие возможности языка LISP.

Алгоритмы на графах имеют и большое практическое значение в информатике. В первую очередь упомянуть применение графов в электронике [2]. И хотя те алгоритмы и реализации, которые мы опишем в данном разделе, едва ли пригодны для решения практически важных задач, мы все же надеемся, что читатель, интересующийся прикладными аспектами программирования на языке LISP, получит представление о достоинствах и недостатках этого языка.

Поскольку главной нашей целью является знакомство с методами программирования на языке LISP, все определения, связанные с теорией графов, будут даны лишь в той мере, в какой это необходимо для изложения. Дополнительные сведения по теории графов можно найти в книгах [3-12]. В качестве введения в комбинаторные алгоритмы можно рекомендовать [4, 7, 8, 11].

⁽¹⁾Крюков А.П., Радионов А.Я., Таранов А.Ю., Шаблыгин Е.М. Программирование на языке R-Лисп. - М.: Радио и связь, 1991. - 192 с.
⁽²⁾Ульман Дж. Вычислительные аспекты СБИС. - М.: Радио и связь, 1990. - 480 с.
⁽³⁾Пападимитриу Х., Стайнглиц К. Комбинаторная оптимизация. - М.: Мир, 1985. - 512 с.
⁽⁴⁾Липский В. Комбинаторика для программистов: Пер. с польск. - М.: Мир, 1988. - 213 с.
⁽⁵⁾Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986. - 272 с.
⁽⁶⁾Евстигнеев В.А. Применение теории графов в программировании. - М.: Наука, 1985. - 352 с.
⁽⁷⁾Оре О. Графы и их применение. - М.: Мир, 1965.- 174 с.
⁽⁸⁾Харари Ф. Теория графов. - М.: Мир, 1973. - 300 с.
⁽⁹⁾Зыков А.А. Основы теории графов. М.: Наука, 1987. - 384 с.
⁽¹⁰⁾Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука, 1990. - 384 с.
⁽¹¹⁾Уилсон Р. Введение в теорию графов. - М.: Мир, 1977. - 207 с.
⁽¹²⁾Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 с.

На следующем шаге мы приведем общие сведения о графах.

Предыдущий шаг Содержание Следующий шаг