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