Представление ориентированных графов

Для представления ориентированных графов можно использовать различные структуры данных. Выбор структуры данных зависит от операторов, которые будут применяться к вершинам и дугам орграфа.

Одним из часто используемых способов представления орграфа G=(V, E) является матрица смежности. Предположим, что множество вершин орграфа V={1, 2, … n}, тогда матрица смежности графа G – это матрица А размера n n со значениями булевого типа, где А[i, j]=true тогда и только тогда, когда существует дуга из вершины i в вершину j. Часто в матрице смежности значение true заменяется на 1, а значение false – на 0. Время доступа к элементам матрицы смежности зависит от размеров множества вершин и множества дуг. Представление орграфа в виде матрицы смежности удобно применять в тех алгоритмах, в которых надо часто проверять существование данной дуги.

С помощью матрицы смежности можно представлять и помеченные орграфы. В этом случае элемент А[i, j] равен метке дуги i j. Если дуги от вершины i к вершине j не существует, то значение А[i, j] может рассматриваться как пустая ячейка. На рис. 7.2 изображен помеченный орграф и соответствующая ему матрица смежности.

Рис. 7.2 – Помеченный орграф и соответствующая ему матрица смежности

Основной недостаток матриц смежности заключается в том, что она требует объема памяти, равного даже если дуг значительно меньше, чем . Поэтому для чтения матрицы или нахождения в ней необходимого элемента требуется время порядка , что не позволяет создавать алгоритмы с временем n для работы с орграфами, имеющими порядка n дуг.

Поэтому вместо матриц смежности могут использовать представления орграфов с помощью списков смежности. Списком смежности для вершины i называется список всех вершин, смежных с вершиной i, причем упорядоченный определенным образом. Таким образом, орграф G можно представить посредством массива HEAD, чей элемент HEAD[i] является указателем на список смежности вершины i. Представление орграфов с помощью списков смежности требует для хранения объем памяти, пропорциональный сумме количества вершин и количества дуг. Если количество дуг имеет порядок n, то общий объем необходимой памяти имеет такой же порядок. Но и для списков смежности время поиска определенной дуги может иметь порядок n, т.к. такой же порядок может иметь количество дуг у определенной вершины. На рис. 7.3 показана структура данных, представляющая орграф с рис. 7.1 посредством связанных списков смежности. Если дуги имеют метки, то их можно хранить в ячейках связанных списков. Для вставки и удаления элементов в списках смежности необходимо иметь массив HEAD, содержащий указатель на ячейки заголовков списков смежности, но не сами смежные вершины.