На головну

 ОСНОВНІ ПОНЯТТЯ |  ВИЗНАЧЕННЯ |  матриці суміжності |  ВИЗНАЧЕННЯ |  Доведення |  ВИЗНАЧЕННЯ |  ТЕОРЕМА 5.3 |  ВИЗНАЧЕННЯ |  ВИЗНАЧЕННЯ |  ВИЗНАЧЕННЯ |

списки суміжності

  1.  VII. тюремний СПИСКИ
  2.  двусвязного списки
  3.  Двохзв'язной СПИСКИ І КІЛЬЦЯ
  4.  додаткові списки
  5.  Завдання № 1. Списки.
  6.  Лабораторна робота № 8. Динамічні структури даних. списки
  7.  Матриця суміжності. Матриця інціденцій. Визначення найкоротша відстань між вершинами графа.

Даний спосіб представлення графів в значній мірі позбавлений надмірності, властивою табличним уявленням.

нехай G = (V, U) - Деякий граф, для якого

V= {v1, ..., vn} і U= {u1, ..., uk}.

Утворюємо два масиви, які позначимо як Aи B.

масивA складається з n елементів, по одному для кожної вершини графа, а B - Стільки елементів, скільки існує решт різних ребер в G.

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

Для графа, зображеного на рис. 5.3., Такі списки мають вигляд:

 вершина  перелік
 a b c d e f  L (a) = f c bL (b) = dL (c) = eL (d) = d b fL (e) = L (f) = d

тут список L(e) Є порожнім.

елементи списків L(v1) -L(vn) Послідовно записуються в масив B.

У перший, другий і наступні елементи масиву A поміщаються значення номерів елементів в B, Які є в масиві B началами списків L(v1), L(v2) і т.д.

Якщо при цьому деякий список L(vi) Виявляється порожнім, значення посилання в елементі A(i) Вважається рівним 0. Таке уявлення графів є повним, оскільки в ньому елементами масиву A представлені всі вершини, а масив B являє все ребра графа. Безліч ребер, що виходять з довільної вершини vi представлено своїми кінцями в частині масиву B, Що починається з елемента A(i) І закінчується або в елементі A(j) - 1, де j = min t ( t > i & A(t) ? 0), або в останньому елементі масиву B.

Для розглянутого графа масивиAи B мають вигляд:

A 1 4 5 6 0 9

 



 матриці інціденцій |  B f c b d e d b f d
© um.co.ua - учбові матеріали та реферати