Способы представления графов в компьютере
Конструирование структур данных для представления в программе объектов математической модели - это основа искусства практического программирования. Далее приводится четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они так или иначе основаны на тех базовых идеях.
Требования к представлению графов:
Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скорость выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи.
Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов.
Матрица смежности
Представление графа с помощью квадратной булевой матрицы М, отражающей смежность вершин, называется матрицей смежности, где
Для матрицы смежности n(p,q) = .
Замечание
Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.
Матрица инциденций
Представление графа с помощью матрицы Н, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа
а для орграфа
Для матрицы инциденций n(p,q) = О(pq).
Списки смежности
Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей на списки смежных вершин, где элемент списка представлен структурой
N : record v : 1..р; n N end record,
называется списком смежности. В случае представления неориентированных графов списками смежности n(p,q) = О(p+2q), а в случае ориентированных графов n(p,q) = О(p+q).
Массив дуг
Представление графа с помощью массива структур Е : array [1 ..q] of record b,e : 1 ..p end record, отражающего список пар смежных вершин, называется массивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q) = О(2q).
