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

⚡ Розумний підсумок

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

  • 📐 Список суміжності: Масив із V зв'язаних списків, де кожен список з індексом i зберігає кожну вершину, суміжну з вершиною i, що дає O(V + E) пам'яті.
  • 🗺️ Матриця суміжності: Двовимірний масив AV × V, де matrix[i][j] містить вагу ребра або 1, коли ребро існує між вершиною i та вершиною j.
  • ⚡ Швидкість пошуку: Матриця суміжності відповідає на запитання «чи є ребро між i та j?» за час O(1), тоді як список суміжності потребує часу O(ступенів) для сканування списку сусідів.
  • 💾 Пам'ять: Матриця суміжності завжди споживає O(V²) пам'яті навіть для розріджених графів, тоді як список суміжності масштабується залежно від фактичної кількості ребер.
  • 🔍 Найкраще підходить: Оберіть матрицю суміжності для щільних графів з частими запитами до ребер та список суміжності для розріджених графів та робочих навантажень з інтенсивним обходом.
  • 🛠️ Область застосування: Обидва представлення працюють на базі BFS, DFS, методів Дейкстри, PageRank, маршрутизації дорожньої мережі та конвеєрів графових нейронних мереж, що використовуються в системах штучного інтелекту.

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

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

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

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

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

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

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

Нехай граф містить 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)
Перебирати сусідів iO(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, за замовчуванням використовують списки суміжності, оскільки більшість реальних графів — соціальні мережі, дорожні карти, веб-сторінки, залежності пакетів — є розрідженими та потребують багато обходу.

Поширені запитання

Список суміжності — це масив із V зв'язаних списків, де кожен список з індексом i зберігає кожну вершину, суміжну з вершиною i. Використання пам'яті становить O(V + E), що підходить для розріджених графів та алгоритмів обходу, таких як BFS та DFS.

Матриця суміжності — це двовимірний масив розміру V × V, де матриця[i][j] містить вагу ребра або 1, якщо ребро існує між вершиною i та вершиною j. Пошук ребра займає O(1), але пам'ять завжди займає O(V²).

Матриця суміжності відповідає на запити існування ребер за O(1). Список суміжності ітерує сусідів за O(ступінь), що швидше для алгоритмів обходу, таких як BFS, DFS та Дейкстра. Найкращий вибір залежить від операцій, які домінують у вашому робочому навантаженні.

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

Використовуйте матрицю суміжності, коли граф щільний, коли множина вершин фіксована, і коли алгоритм неодноразово запитує одне й те саме ребро. Матриця Флойда-Воршелла та транзитивне замикання працюють природно на матрицях суміжності.

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

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

Так. GitHub Copilot та ChatGPT генерують список суміжності та шаблон матриці для Python, C++ та JavaРозробникам все ще потрібно перевіряти крайові випадки, такі як дублікати ребер, самоцикли та правильну обробку орієнтованих або зважених графів.

Підсумуйте цей пост за допомогою: