Представление графов в ЭВМ
1.1. Представление графов в ЭВМ
Следует подчеркнуть, что конструирование структур данных для представления в программе объектов математической модели - это основа искусства практического программирования. Мы приводим два различных базовых представления графов.
Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они, так или иначе, основаны на тех базовых идеях, которые описаны в этом разделе.
1.1.1. Требования к представлению графов
Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами.
Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены два из наиболее часто используемых представления.
Указанные представления пригодны для графов и орграфов, а после некоторой модификации также и для псевдографов, мультиграфов.
Представления иллюстрируются на конкретных примерах графа G и орграфа D, диаграммы которых представлены на рис. 7.10.
Рекомендуемые материалы
Рис. 3.9. Диаграммы графа (слева) и орграфа (справа), используемых в качестве примеров
1.1.2. Матрица смежности
Представление графа с помощью квадратной булевской матрицы
отражающей смежность вершин, называется матрицей смежности, где
Пример
1.1.3. Матрица инциденций
Лекция "10 Переход от природного к надприродному" также может быть Вам полезна.
Представление графа с помощью матрицы Н: array [l..p, l..q] of 0..1 (для орграфов Н: array [l..p, l..q] of -1..1), отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа:
а для ориентированного графа
Пример