2. Способи задання графів

Існує два основних підходи до задання графів: послідовний і зв'язний.

Послідовна форма використовує квадратну таблицю, яку називають матрицею суміжності. Для неорієнтованого графу матриця суміжності Graf(1:n, 1:n) визначається так: Graf(і, j)=1, якщо (i,j)  Е і Graf (i,j)=0 – в іншому випадку. У разі навантаженого графу Graf(i,j) = вартість ребра (і,j) якщо ребро існує, та Graf(i,j) = + у разі відсутності ребра (і,j) в G=(V,E). Аналогічно задається й орієнтований граф, але з урахуванням орієнтації ребер. На рис. 3 продемонстровано задання матрицями суміжності неорієнтованого і орієнтованого графів з рис. 2.

За такого задання нам потрібно зробити О (п²) операцій по заповненню таблиці. Тому всі алгоритми, які використовують послідовну форму задан­ня графу, не можуть мати часових оцінок, кращих за О (n²).

Введемо позначення: якщо множина V складається з п вершин, тоді |V| = п, аналогічно |Е|=т. У теорії графів для задання графу викорис­товують матрицю інцидентності. Вона має розмірність п  т, де |V|=п, |Е|=т. Для орієнтованого графу стовпець, що відповідає дузі <и, v>  Е, містить 1 в рядку, що відповідає вершині u, та 0 в рядку v і нулі в інших рядках. У разі неорієнтованого графу стовпець, що відповідає ребру (u, v), містить 1 в рядках, що відповідають u та v, і нулі в інших рядках. З погляду програмування такий спосіб задання графу потребує п  т комірок пам'я­ті, він незручний для організації доступу до інформації. Наприклад, для побудови відповіді на запитання типу "існує дуга (u, v)?" в найгіршому випадку потрібно переглянути всі т стовпців.

Рис. 3. Матриці суміжності графів

Тому існує інша форма задання графу, яку називають списком зв'яз­ності. Граф G з п вершинами буде задаватися п списками – по одному для кожної вершини і. Список для вершини і містить вершини, суміжні з і. На рис. 4 показані списки суміжності для графів з рис. 2.

Списки суміжності можуть бути задані масивом VERTEX(1:р), де Р=е, якщо граф орієнтований, i р = 2е в неорієнтованому графі, а е=|Е|. Head (i), 1 і  п дає початкові вершини околу суміжності для вершини і. Якщо ми визначимо Head(п+1)=р+1, тоді вершини списку суміжності для вершини і запам'ятовуються в VERTEX(j), де Head(і) <j< Head(i+1). Якщо список суміжності для вершини і пустий, тоді Head(і)=Head(i+1). На рис. 5 продемонстровано послідовне задання списків суміжностей з рис.4.

Рис. 4. Списки суміжності

Рис. 5. Послідовне задання списків суміжностей із рис. 4

Зазначимо, що в класичному списку суміжності для неорієнтованих графів кожне ребро (u, v) задається подвійно: через вершину u в списку початок [u] і через вершину v в списку початок [v]. Для багатьох алгорит­мів на графах характерною є динамічна модифікація ребер, їх видалення і додавання. Тому в цих випадках у вузлах списків суміжності потрібно мати додаткові поля, що забезпечуватимуть ефективність реалізації наве­дених операцій. Найбільш використовуваними є такі поля: покажчик на попередній елемент, вузол початок [v], що має серед своїх елементів вер­шину u, покажчик на вузол початок [u].