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

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

список в java

Характеристики списку суміжності:

• Розмір матриці визначається кількістю вузлів у мережі.
• Кількість ребер графа легко обчислити.
• Список суміжності - це a зубчастий масив .

Як створити список суміжності?

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

• Створіть масив пов’язаних списків розміру Н , де N – кількість вершин у графі.
• Створіть пов’язаний список суміжних вершин для кожної вершини в графі.
• Для кожного краю (u, v) у графі доп в до пов’язаного списку в , і додати в до пов’язаного списку в якщо граф неорієнтований, інакше додайте в до списку в якщо воно спрямоване з в до в . (У випадку зважених графів зберігайте вагу разом із зв’язками).

Застосування списку суміжності:

• Алгоритм Дейкстри , Пошук спочатку вшир , і Пошук спочатку на глибину використовувати списки суміжності для представлення графів.
• Обробка зображення : Списки суміжності можна використовувати для представлення зв’язків суміжності між пікселями на зображенні.
• Розробка гри : ці списки можна використовувати для зберігання інформації про зв’язки між різними областями або рівнями, на яких розробники ігор використовують графіки для представлення ігрових карт або рівнів.

Переваги використання списку суміжності:

• Список суміжності простий і зрозумілий.
• Додавати або видаляти ребра з графіка швидко й легко.

Недоліки використання списку суміжності:

• У списках суміжності доступ до ребер може тривати довше, ніж до матриці суміжності.
• Вона вимагає більше пам’яті, ніж матриця суміжності для щільних графів.

Що ще можна почитати?

• Значення та визначення матриці суміжності в DSA
• Додавання та видалення ребер у представленні списку суміжності графа
• Перетворення матриці суміжності на представлення списку суміжності графа
• Перетворення списку суміжності на представлення матриці суміжності графа
• Порівняння між представленням списку суміжності та матриці суміжності графа