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

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

Одним из наиболее общих представлений является матрица смежности.

Предположим, что граф состоит из n вершин. Матрицей смежности для этого орграфа будет матрица А размера nxn со значениями булевого типа, где А[i][j]=true тогда и только тогда, когда существует дуга из вершины i в вершину j.

	1	2	3	4
1	0	1	1	0
2	0	0	0	1
3	0	1	0	0
4	0	0	1	0

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

Обобщением описанного представления орграфа можно считать представление помеченного орграфа также посредством матрицы смежности, но у которой элемент A[i][j] равен метке дуги i j. Если дуги от i к j не существует, то значение A[i][j] не может быть значением какой-либо допустимой метки, а может рассматриваться как «пустая» ячейка.

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

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

Т.О. орграф G можно представить посредством массива HEAD, чей элемент HEAD[i] является указателем на список смежности вершины i.

Т акое представление орграфа требует для хранения объем памяти, пропорциональный сумме количества вершин и количества дуг.

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

Если известно, что граф не будет подвергаться изменениям или они будут незначительны, то предпочтительно сделать массив HEAD массивом курсоров на массив ADJ, где ячейки ADJ[HEAD[i]] и т.д. содержат вершины, смежные с вершиной i, и эта последовательность смежных вершин заканчивается первым встреченным 0. Пример такого представления для нашего графа:

Атд для ориентированных графов

Наиболее общие операторы, выполняемые над ориентированными графами это:

• операторы чтения меток вершин и дуг,

• операторы вставки и удаления вершин и дуг,

• операторы перемещения по последовательностям дуг.

Часто в программах встречаются операторы, которые неформально можно описать следующим образом:

for (каждая вершина w, смежная с вершиной v) { некоторые действия с вершиной w }

Для реализации такого оператора необходим индексный тип данных для работы с множеством вершин, смежных с v.

Например, если для представления орграфа используются списки смежности, то индекс – это позиция в списке смежности вершины v. Если применяется матрица смежности, тогда индекс – целое число, соответствующее смежной вершине.

Для просмотра множества смежных вершин необходимы следующие три оператора:

1. FIRST(v) возвращает индекс первой вершины, смежной с v. Если вершина v не имеет смежных вершин, то возвращается нулевая вершина Л.

2. NEXT(v,i) возвращает индекс вершины, смежной с v, следующий за индексом i. Если i – это индекс последней смежной вершины, то возвращается Л.

3. VERTEX(v,i) возвращает вершину с индексом i из множества вершин, смежных с v.

Пример. Если для представления орграфа используется матрица смежности, то функция VERTEX просто возвращает индекс i. 0 в этой матрице означает отсутствие дуги.

А функции FIRST и NEXT имеют вид:

int FIRST(int v)

{

int i;

for(i=0; i<n; i++)

if (a[v][i])

return i;

return -1; /* вершина v не имеет смежных вершин */

}

int NEXT(int v, int i)

{

int j;

for(j = i+1; j < n; j++)

if(a[v][j]) return j;

return -1;

}

Эти функции позволяют реализовать последовательный просмотр вершин, смежных с вершиной v так:

for (i = FIRST(v); i!=-1; i = NEXT(v,i))

{

w = VERTEX(v,i);

/* действия с вершиной w */

}