Пригадайте, як ви подавали графи під час вивчення математики та інших навчальних дисциплін.

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

Подання графів за допомогою матриць суміжності. Матриця суміжності для графу з n ершинами подається двовимірним масивом розмірністю n*n.

Якщо вершина i неорієнтованого незваженого графу має ребро з вершиною j, то елемент масиву mas[i, j] набуває значення 1, інакше — 0.

Розробимо матрицю суміжності для неорієнтованого графу, зображеного на рис. 8.10.

Матрицю суміжності для неорієнтованого незваженого графу наведено на рис. 8.11.

Для орієнтованого незваженого графу елементи матриці суміжності набувають значення 1, якщо відповідне ребро виходить з вершини, інакше — значення 0.

На рис. 8.12 ребро виходить із вершини 1 у вершини 2 і 3, тому елементи mas[1, 2] і mas[1, 3] набувають значення 1, а елемент mas[2, 1] — значення 0.

Матрицю суміжності для орієнтованого незваженого графу (див. рис. 8.12) наведено на рис. 8.13.

Розглянемо подання орієнтованого зваженого графу (рис. 8.14). Матрицю суміжності для цього графу наведено в таблиці на рис. 8.15. Як бачимо, елементи матриці набувають значень ваги відповідних ребер.

Подання графів за допомогою списку суміжних вершин. Для кожної вершини складається список суміжних вершин. Наприклад, для графу (див. рис. 8.12) список суміжних вершин можна записати так:

1 – 2 – 3

2 – 4

3 – 2

4 – 3

5 – 2 – 4

Для зваженого графу біля суміжної вершини вказується вага ребра. Наприклад, для графу (див. рис. 8.14) список можна записати так:

1 – 2(8) – 4(15) – 5(3)

2 – 3(5)

3 – 5(17)

4 – 3(13) – 5(9)

5 –