Граф Структура даних і Algorithms (Приклад)
Сара Чен
⚡ Розумний підсумок
Графова структура даних (Graf Data Structure) — це нелінійна колекція вершин і ребер, де кожне ребро з'єднує пару вершин. Графи моделюють реальні мережі, такі як карти, соціальні зв'язки та веб-сторінки, і підтримують багато потужних алгоритмів.
Що таке графік у структурі даних?
Граф — це нелінійна структура даних, що складається з вершин і ребер, де вершини містять інформацію або дані, а ребра виконують роль зв'язку між парою вершин.
Він використовується для вирішення реальних проблем, таких як пошук найкращого маршруту до місця призначення та маршруту для телекомунікацій та соціальних мереж. Користувачі вважаються вузлом у графі, а дроти – ребрами, що з'єднують користувачів.
Якщо ребра представлені як E, а вершини представлені як V, то граф G можна записати як набір вершин і ребер, наприклад Г (В, Е).
Приклад графіка в структурі даних
Ось простий приклад структури даних у вигляді графа:
Це простий неорієнтований граф (один з видів графа). Тут множина вершин така: {A, B, C, D, E, F}. Дві вершини утворюють ребро. Наприклад, A та B з'єднані ребром. Однак A та F не з'єднані жодними ребрами.
Термінології графів у структурі даних
Нижче наведено деякі важливі терміни, що використовуються в структурі даних графа:
| Термін | Опис |
|---|---|
| Вершина | Кожен елемент даних називається вершиною або вузлом. На зображенні вище A, B, C, D та E є вершинами. |
| Край (дуга) | З'єднувальні ланки між двома вузлами або вершинами називаються ребром (дугою). Воно має два кінці та представлене як (початковаВершина, кінцеваВершина). |
| Ненаправлений край | Це двонаправлений край. |
| Спрямований край | Це односпрямований край. |
| Зважений край | Ребро зі значенням на ньому. |
| Ступінь | У графі кількість ребер, з'єднаних з вершиною, називається степенем. |
| Indegree | Загальна кількість вхідних ребер, з’єднаних з вершиною. |
| Попередня ступінь | Загальна кількість вихідних ребер, з’єднаних з вершиною. |
| Автопетля | Ребро називається автопетлею, якщо два його кінці збігаються. |
| Суміжність | Вершини називаються суміжними, якщо між ними з'єднане ребро. |
Типи графів у структурі даних
Ось список найпоширеніших типи графів у структурі даних:
- Орієнтований граф
- Неорієнтований графік
- Зважений графік
- Двонаправлений графік
- Нескінченний графік
- Нульовий графік
- Тривіальний граф
- Мультиграф
- Повний графік
- Підключений граф
- Циклічний графік
- Спрямований ациклічний графік (DAG)
- Графік циклу
- Дводольний граф
- Графік Ейлера
- Графік Гамільтона
Як представити граф у структурі даних?
Граф зазвичай зберігається в пам'яті за допомогою одного з двох представлень. Вибір впливає на обсяг пам'яті, який використовує графік, і на швидкість виконання поширених операцій.
- Матриця суміжності: Двовимірний масив V × V, де комірка [i][j] дорівнює 1 (або вазі ребра), якщо ребро існує між вершиною i та вершиною j, та 0 в іншому випадку. Він дозволяє пошук ребер O(1), але використовує простір O(V²), що робить його найкращим для щільних графів.
- Список суміжності: Масив списків, де кожна вершина зберігає список сусідніх вершин. Він використовує простір O(V + E) та ефективний для розріджених графів, тому більшість реальних графів використовують його.
Більше про них ви можете прочитати в список суміжності та матричне представлення графа навчальний посібник.
Застосування структури даних графа
Граф має багато варіантів використання. Існує багато алгоритмів, які використовують графи. Ось деякі із застосувань графа:
- Google Карти використовують графіки для знаходження перетину двох доріг та обчислення відстані між двома місцями. Наприклад Дейкстра, для знаходження найкоротшої відстані між місцем відправлення та місцем призначення.
- Facebook використовує Graphs для пошуку спільних друзів користувачів. Його алгоритм розглядає кожного користувача як вузол графу.
- Для розподілу ресурсів використовується DAG (спрямований ациклічний граф). Він перевіряє залежність ресурсів.
- Команда Google Пошукова система використовує графіки для створення рейтингу веб-сайтів.
- Мапаping Пристрій використовує структуру даних графа.
- A маршрутизатор а його протокол використовує Graph для вивчення шляху до пункту призначення.
