Представление графов в ЭВМ
Следует подчеркнуть, что конструирование структур данных для представления в программе объектов математической модели - это основа искусства практического программирования. Мы приводим два различных базовых представления графов.
Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они, так или иначе, основаны на тех базовых идеях, которые описаны в этом разделе.
Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами.
Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены два из наиболее часто используемых представления.
Указанные представления пригодны для графов и орграфов, а после некоторой модификации также и для псевдографов, мультиграфов.
Представления иллюстрируются на конкретных примерах графа G и орграфа D, диаграммы которых представлены на рис. 7.10.
Рис. 3.9. Диаграммы графа (слева) и орграфа (справа), используемых в качестве примеров