Способы представления графов в памяти ЭВМ

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

5.2.1.Матрица смежностей графа

    Одним из наиболее общих представлений орграфа G = (V, Е) является матрица смежности. Предположим, что множество вершин V= {1, 2,..., n}. Матрица смежности для орграфа G — это матрица разме­ра n х n со значениями булевого типа, где A[i,j] = true  тогда и только тогда, когда существует дуга из вершины i в вершину j. Часто в матрицах смежности значение true  заменяется на 1, а значение false  —  на 0. Время доступа к элементам матрицы смежности зависит от размеров множества вершин и множества дуг. Представление орграфа в виде матрицы смежности удобно применять в тех алгоритмах, в которых надо часто проверять существование данной дуги. Для мультиграфа вместо 0 или 1 указывается число, равное кратности ребер. На рис. 12 показаны матрицы смежностей: для орграфа на рис. 1,а – а, для неорграфа на рис. 11,б – б, для мультиграфа на рис. 2,а – в, для наглядности вместо 0 стоит «пустая ячейка.

 

	1	2	3	4	5	6				1	2	3	4	5	6				1	2	3	4	5	6
1		1							1				1	1	1			1		1		2
2				1	1				2				1	1	1			2					1
3									3						1			3
4	1				1				4	1	1							4		2			2
5				1					5	1	1							5				2
6			1			1			6	1	1	1						6			1
а									б									в

Рис. 12

 

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

    Если на вершинах графа заданы веса, вводится дополнительный массив V длиной N, где элемент v_i содержит значение веса вершин графа с номером i.

    Если на ребрах (дугах) заданы веса, то для неорграфа и орграфа применяется матрица, совпадающая со структурой матрицы смежностей, но значения элементов равны весам соответствующих связей.

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

5.2.2. Матрица инцидентностей графа

    Матрица инцидентностей – прямоугольная матрица В, строки которой соответствуют вершинами, а столбцы – ребрам (дугам) графа. Для неорграфа:

	если ребро Lj є Е инцидентно vi;
	если ребро Lj є Е не инцидентно vi.

Число единиц в i -й строке равно степени вершины v_i графа, а число единиц в любом столбце – 2.

    Для орграфа:

 

	если vi начальная вершина дуги Lj є Е,
	если vi конечная вершина дуги Lj,
	если дуга Lj є Е, не инцидентно vi или образует петлю.

    Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец содержит один элемент, равный 1, и один – равный –1, либо все элементы столбца равны 0.

    Если на вершинах графа заданы веса, то используется дополнительный массив V длиной N, где элемент v_i имеет значение веса вершины графа с номером i, если на ребрах (дугах) заданы веса, то – дополнительный массив W  длиной q, где элемент w_i содержит значение веса ребра (дуги).

    На рис. 13 показаны матрицы инцидентностей для орграфа на рис. 1,а – а, для неорграфа на рис. 11,б – б.

 

	1 2	2 4	2 5	4 1	4 5	5 4	6 3				1 4	1 5	1 6	2 4	2 5	2 6	6 3
1	1	0	1	-1	0	0	0			1	1	0	1	-1	0	0	0
2	-1	1	0	0	0	0	0			2	-1	1	0	0	0	0	0
3	0	0	0	0	0	0	-1			3	0	0	0	0	0	0	-1
4	0	-1	0	1	1	-1	0			4	0	-1	0	1	1	-1	0
5	0	0	-1	0	-1	1	0			5	0	0	-1	0	-1	1	0
6	0	0	0	0	0	0	1			6	0	0	0	0	0	0	1
а										б

Рис. 13

5.2.3. Задание графа массивом преемников вершин
(FO-представление графа)

    В целях экономичного представления графа в памяти ЭВМ часто используют FO -представление графа, позволяющее отобразить матрицу смежностей графа одномерным массивом FO, формирующимся следующим образом: сначала записываются номера вершин (в любом порядке), в которые заходят дуги из первой вершины, затем ставится разделитель 0, далее – номера вершин, в которые заходят дуги из второй вершины, после чего ставится разделитель 0 и т.д. Таким образом, для неорграфа и мультиграфа строится массив FO длиной 2xq+N, так как каждое ребро учитывается дважды, для орграфа и псевдографа – массив FO длиной q+N. Будем считать, что величины N и q заданы и на их основе построен массив FO. Если на вершинах и (или) ребрах (дугах) заданы веса, то применяются дополнительные массивы V(N) и W(q), где элементы v_i и w_j содержат значения весов для вершин v_i и ребра (дуги) l_j.

    Например, одномерный массив FO для орграфа на рис. 1,а имеет вид: , а для неорграфа на рис. 11,б:

.

5.2.4. Задание графа массивом предшественником вершин
(FI-представление)

    Массив FI формируется так: сначала записывают номера вершин (в любом порядке), из которых исходят дуги в первую вершину, затем ставят разделитель 0, далее записывают номера вершин, из которых исходят дуги во вторую вершину, и ставят разделитель 0 и т.д. Таким образом, для неорграфа и мультиграфа строится массив FI длиной 2xq+N, так как каждое ребро учитывается дважды. Для орграфа и псевдографа массив FI имеет длину q+N. Заметим, что для неорграфов и мультиграфов FO и FI представления совпадают.

    Например, одномерный массив FI для орграфа на рис. 1,а имеет вид: .

5.2.5. Модифицированное FO-представление графа
(MFO-представление)

    В MFO -представлении графа вместо разделителей 0 используется дополнительный массив P длиной N, в котором указываются верхние границы окончания списков номеров вершин в массиве G, смежных с заданной вершиной по выходящим дугам. Для неорграфов и мультиграфов длина массива G равна 2xq, а массива P – N. Для орграфов и псевдографов длина массива G  равна q, а массива P – N.

    Для хранения весов вершин и ребер (дуг) применяются дополнительные массивы V  и W, где элементы v_i и w_j содержат значения весов для вершины v_i и ребра (дуги) l_j. Для неорграфов и мультиграфов MFO и FI представления совпадают.

    Например, для орграфа на рис. 1,а массивы G и PMFO -представления графа имеют вид:

    , ,

а для неорграфа на рис. 11,б:

    ,

    .

5.2.6. Модифицированное FI-представление графа
(MFI-представление)

    В отличие от MFO -представления графа в MFI -представлении указывается в массиве P  верхние границы окончания списков вершин, смежных с заданной вершиной по входящим в нее дугам. Например, для орграфа на рис. 1,а MFI- представление графа имеет вид: , , а для неорграфа на рис. 11,б:

,

.

5.2.7. Сокращенные MFО и MFI-представления неорграфов

    В целях экономии памяти обыкновенные графы можно представлять следующим образом: формируют массив FO, в котором сначала записывают номера вершин, смежных с первой вершиной, далее разделитель 0, затем номера вершин, смежных со второй вершиной и номера которых больше двух, а также разделитель 0 и т.д. Результатом является сокращенное FO -представление. Сокращенное MFO -представление получается заменой разделителей 0 на дополнительный массив Р, содержащий верхние границы списка номеров вершин, смежных с заданной вершиной, и больших, чем номер заданной вершины.

    Например, для неорграфа на рис. 11,б сокращенное                   FO- представление имеет вид

    ,

а сокращенное MFO - представление:

    , .