Лекція №16. Машинне представлення графів

Представлення графа списком його ребер

Представлення графа структурою суміжності його вершин

Представлення графа списком суміжності вершин із використанням індексного масиву

Схема зберігання з полем зв’язків

Граф може бути описаний списком його ребер, де кожне ребро представляється парою інцидентних йому вершин. Це представлення можна реалізувати двома масивами.

, де - кількість ребер графа.

Кожний елемент в масиві є мітка вершини, а -те ребро графа виходить з вершини і входить в вершину . Наприклад, для графа, зображеного на малюнку 15.1 машинне представлення має вигляд:

Для співвіднесеного графа:

Дане представлення дозволяє легко представити петлі і кратні ребра.

Орієнтований і неорієнтований граф може бути однозначно представлений структурою суміжності своїх вершин. Структура суміжності складається із списків вершин графа, суміжних з вершиною . Наприклад, побудуємо просту таблицю зв’язків для графа зображеного на малюнку 15.1.

		-
	,
		-
		-
		-

Така таблиця зв’язків може бути дуже неефективною, якщо багато вершин, буде мати ступінь меншу ніж .

Більш економно таку структуру можна реалізувати зберігаючи списки суміжності послідовно в одномірному масиві, наприклад, .

Додатковий індексний масив довжиною містить вказівники початку будь-якого списку суміжності в масиві .

Наприклад, розв’язок деякої задачі звівся до матриці такої структури:

		.	.	.
				.	.
.			.		.
.		.		.
.	.		.
	.	.	.

Рис. 16.1 Структура деякої матриці

Щоб підкреслити відповідність -того діагонального елемента матриці з вершиною її графа, цей елемент вказуємо в кружечку. Недіагональні ненульові елементи позначені зірочкою. Граф, що відповідає такій матриці, має вигляд:

Рис. 16.2 Граф матриці, зображеної на рис. 16.1

Тоді масив суміжності і масив індексів буде мати вигляд:

1 3 6 8 9 11 13

1 2 3 4 5 6 7

- адреса першої вільної комірки в масиві . Загальна довжина масивів при такій схемі зберігання .

Розглянуті схеми мають той недолік, що якщо ступені вершин (вузлів) невідомі (матриця будується динамічно), то неможливо побудувати схему зберігання графа, заданого списком ребер, оскільки невідомі формати окремих списків суміжності. Цю складність долають вводячи поле зв’язків.

Значенням вказівника являється початок списку суміжності -тої вершини, при цьому в масиві знаходимо сусіда вершини , а в масиві - вказівник знаходження наступного сусіда цієї вершини, -в масиві вказує закінчення списку суміжності для вершини .

Загальна довжина масивів при такому способі представлення графів це більше, ніж в попередніх схемах, але при цій схемі зберігання можна легко добавляти ребра. Наприклад, треба додати ребро (3, 6). Змінимо список суміжності вузла 3: =13, =6, =1; вузла 6: =14, =3, =5.