Структура даних графіків

Зміст

Графічна термінологія
Подання графіків
Графічні операції

У цьому підручнику ви дізнаєтеся, що таке структура даних графіків. Крім того, ви знайдете подання графіка.

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

Спробуємо це зрозуміти на прикладі. На facebook все є вузлом. Сюди входять Користувач, Фото, Альбом, Подія, Група, Сторінка, Коментар, Історія, Відео, Посилання, Примітка … все, що має дані, є вузлом.

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

Приклад структури даних графіка

Тоді весь facebook - це сукупність цих вузлів та країв. Це пояснюється тим, що facebook використовує графічну структуру даних для зберігання своїх даних.

Точніше, графік - це структура даних (V, E), яка складається

Збірник вершин V
Колекція ребер E, представлена як упорядковані пари вершин (u, v)

Вершини та ребра

На графіку

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Графічна термінологія

Суміжність : Вершина називається сусідньою з іншою вершиною, якщо між ними є ребро. Вершини 2 і 3 не суміжні, оскільки між ними немає ребра.
Шлях : Послідовність ребер, що дозволяє перейти від вершини A до вершини B, називається контуром. 0-1, 1-2 і 0-2 - це шляхи від вершини 0 до вершини 2.
Направлений графік : Графік, в якому ребро (u, v) не обов'язково означає, що існує також ребро (v, u). Ребра на такому графіку представлені стрілками, щоб показати напрямок ребра.

Подання графіків

Графіки зазвичай представлені двома способами:

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

Матриця суміжності - це 2D-масив з вершин V x V. Кожен рядок і стовпець представляють вершину.

Якщо значення будь-якого елемента a(i)(j)дорівнює 1, це означає, що існує ребро, що з'єднує вершину i і вершину j.

Матриця суміжності для графіку, який ми створили вище, є

Матриця суміжності графіків

Оскільки це ненаправлений графік, для ребра (0,2) нам також потрібно позначити ребро (2,0); роблячи матрицю суміжності симетричною щодо діагоналі.

Пошук краю (перевірка, чи існує ребро між вершиною A і вершиною B) надзвичайно швидкий у поданні матриці суміжності, але нам потрібно зарезервувати простір для кожного можливого зв’язку між усіма вершинами (V x V), тому для цього потрібно більше місця.

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

Список суміжності представляє графік як масив пов’язаних списків.

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

Список суміжностей для графіку, який ми створили у першому прикладі, є таким:

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

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