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

Хоча всі вони виглядають по-різному типи графіків можна представити подібним чином. Зазвичай існує два типи графічного представлення:
- Матриця суміжності
- Список суміжності
Список суміжності
Список суміжності складається зі зв'язаних списків. Кожна вершина вважається індексом масиву, а кожен елемент представляє зв'язаний список. Ці зв'язані списки містять вершини, які мають спільне ребро з вершиною індексу.
Ось приклад списку суміжності:
Нехай граф містить V вершин та E ребер. Просторова складність списку суміжності дорівнює O(V + E), яка масштабується з кількістю дійсних ребер, а не з кожною можливою парою вершин.
У найгіршому випадку складність простору стає O(V²) якщо заданий граф є повним графом, оскільки кожна вершина тоді з'єднується з кожною іншою вершиною.
Матриця суміжності
Матриця суміжності складається з двовимірного масиву. Для графа з V вершинами розмір матриці буде V × V.
Казати 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. Решта комірок у рядку E будуть заповнені нулями.
Ось кілька моментів, на які варто звернути увагу:
- Граф не має самоциклів, коли первинна діагональ матриці суміжності дорівнює 0.
- Графік є орієнтованим, якщо комірки в точках (a, b) та (b, a) не містять однакових значень. В іншому випадку графік є неорієнтованим.
- Графік є зваженим, якщо значення будь-якої комірки більше 1.
Основна проблема матриці суміжності полягає в тому, що вона вимагає квадратного простору. Навіть ребра, яких не існує, все одно виділяють комірки в пам'яті.
Наприклад, якщо у нас є граф зі 100 вузлами, то для його зберігання потрібно 10 000 комірок. Оперативна пам'ятьЗ меншою кількістю ребер у графі виділення такої великої кількості пам'яті може бути марнотратним. Отже, просторова складність з використанням матриці суміжності становить O(N²), де N – кількість вузлів у графі.
Список суміжності проти матриці суміжності
Перш ніж вибрати представлення, корисно порівняти обидві моделі пліч-о-пліч з операціями, які домінують у реальних графових робочих навантаженнях:
| Operaції | Матриця суміжності | Список суміжності |
|---|---|---|
| Складність простору | O(V²) | O(V + E) |
| Додати вершину | O(V²) | O (1) |
| Додати край | O (1) | O (1) |
| Видалити край | O (1) | O(E) |
| Перевірити, чи існує ребро (i, j) | O (1) | O (ступінь i) |
| Перебирати сусідів i | O(V) | O (ступінь i) |
| Найкраще для | Щільні графи, часті запити до ребер | Розріджені графи, завдання з великим обсягом обходу |
Коротше кажучи, матриця суміжності виграє при пошуку ребер за постійний час, тоді як список суміжності виграє при ітерації пам'яті та сусідів, тому такі алгоритми, як BFS, DFS та Дейкстра, зазвичай поєднуються зі списками суміжності.
Переваги та недоліки графового представлення
Кожне представлення має свої недоліки. Знання сильних і слабких сторін обох моделей допомагає вам вибрати правильну для вирішення проблеми.
Переваги матриці суміжності:
- Запити на існування ребер O(1) між будь-якою парою вершин за постійний час.
- Фіксоване індексування спрощує реалізацію матричних алгоритмів, таких як Флойд-Воршелл та транзитивне замикання.
- Зважені ребра природно вписуються в одну комірку матриці.
Недоліки матриці суміжності:
- Витрачає O(V²) пам'яті, коли граф розріджений.
- Додавання нової вершини вимагає зміни розміру всієї матриці.
- Ітерація по сусідах однієї вершини займає O(V), навіть коли вершина має лише кілька ребер.
Переваги списку суміжності:
- Використовує лише O(V + E) пам'яті, що близько до реальної кількості ребер у розріджених графах.
- Додавання нової вершини або ребра це O(1).
- Алгоритми обходу, такі як BFS та DFS, ітерують сусідів за O(ступінь), що дає загальний час виконання O(V + E).
Недоліки списку суміжності:
- Перевірка існування певного ребра займає час O(градусів) замість O(1).
- Локальність кешу слабша, оскільки зв'язані списки розкидані по пам'яті.
- Зважені ребра потребують супутнього поля або списку пар, що дещо ускладнює структуру даних.
Коли використовувати список суміжності проти матриці суміжності
Вибір представлення залежить від щільності графа та операцій, які ви виконуєте найчастіше. Скористайтеся цим коротким посібником, щоб вибрати правильну структуру:
- Віддайте перевагу матриці суміжності коли граф щільний (E близький до V²), коли ребра рідко змінюються, і коли ваш алгоритм багато разів запитує «чи є ребро між i та j?».
- Віддати перевагу списку суміжності коли граф розріджений (E набагато менше за V²), коли множина вершин або ребер зростає під час виконання, і коли ви проходите граф за допомогою BFS, DFS або Алгоритм пошуку найкоротшого шляху Дейкстри.
- Віддайте перевагу змішаній моделі (список суміжності плюс хеш-набір ребер), коли вам потрібна як швидка ітерація сусідів, так і запити на ребра O(1), ціною додаткової пам'яті.
Сучасні бібліотеки графів, такі як NetworkX та igraph, за замовчуванням використовують списки суміжності, оскільки більшість реальних графів — соціальні мережі, дорожні карти, веб-сторінки, залежності пакетів — є розрідженими та потребують багато обходу.


