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

Хоча всі вони виглядають по-різному типи графіків можна представити подібним чином. Загалом існує два типи графічного представлення:

1. Матриця суміжності
2. Список суміжності

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

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

Ось приклад списку суміжності:

Скажімо, граф містить V кількість вершин і E кількість ребер.

Загалом, космічна складність буде O(V + E).

У найгіршому випадку складність простору буде O(V2) якщо заданий граф є повним графом

Матриця суміжності

Матриця суміжності складається з двовимірного масиву. Граф, що має V кількість вершин, розмір матриці буде VxV.

Казати, matrix[i][j] = 5. Це означає, що між вузлом i і j є межа, вага якої дорівнює 5.

Давайте подивимося на наступний граф і його матрицю суміжності:

Ми створили 2D масив використовуючи ці кроки:

Крок 1) Вершина A має пряме ребро з B, а вага дорівнює 5. Отже, клітинка в рядку A і стовпці B буде заповнено 5. Решта клітинок у рядку A буде заповнено нулями.

Крок 2) Вершини B мають пряме ребро з C, а вага дорівнює 4. Отже, клітинка в рядку B і стовпці C буде заповнено 4. Решта клітинок у рядку B буде заповнено нулем, оскільки B не має вихідного ребра до жодної інші вузли.

Крок 3) Вершини C не мають прямих ребер з іншими вершинами. Отже, рядок C буде заповнено нулями.

Крок 4) Вершина D має спрямоване ребро з A і C.

• Тут клітинка в рядку D і стовпці A матиме значення 7. Комірки в рядку D і стовпці C матимуть значення 2.
• Решта клітинок у рядку D будуть заповнені нулями.

Крок 5) Вершини E мають спрямоване ребро з B і D. Комірка в рядку E і стовпці B матиме значення 6. Комірки в рядку E і стовпці D матимуть значення 3. Решта клітинок у рядку D будуть заповнений нулями.

Ось кілька моментів, на які варто звернути увагу:

• Граф не має самоциклів, коли первинна діагональ матриці суміжності дорівнює 0.
• Граф є орієнтованим графом, якщо індекси (a,b) і (b,a) не мають однакові значення. В іншому випадку граф є орієнтованим графом.
• Графік буде зваженим, якщо значення комірок більше 1.

Є певна проблема з матрицею суміжності, оскільки вона вимагає квадратних проміжків. Тут ми зберігаємо не з’єднані ребра. Ці ребра виділяють місце в пам'яті.

Наприклад, якщо у нас є граф із 100 вузлами, то для його зберігання в Оперативна пам'ять. З меншою кількістю ребер у графі виділення такої великої пам’яті може бути марною тратою. Таким чином, складність простору з використанням матриці суміжності буде O(N2), де N означає кількість вузлів у графі.