Граф Структура даних і Algorithms (Приклад)
Сара Чен
Що таке графік у структурі даних?
Граф — це нелінійна структура даних, яка складається з вершин і ребер, де вершини містять інформацію або дані, а ребра працюють як зв’язок між парою вершин.
Він використовується для вирішення реальних текстових задач, як-от пошук найкращого маршруту до пункту призначення та маршруту для телекомунікацій і соціальних мереж. Користувачі вважаються вузлом у Графі, а дроти — ребрами, що з’єднують користувачів.
Якщо ребра представлені як E, а вершини представлені як V, то граф G можна записати як набір вершин і ребер, наприклад G (V, E)
Приклад графіка в структурі даних
Ось простий приклад структури даних графіка:
Це простий неорієнтований граф (один вид графа). Тут набір вершин: {A, B, C, D, E, F}. Дві вершини утворюють ребро. Наприклад, A і B пов'язані ребром. Однак A і F не пов'язані жодними ребрами.
Термінології графів у структурі даних
Нижче наведено деякі важливі терміни, які використовуються в структурі даних графіка:
| Термін | Опис |
|---|---|
| Вершина | Усі елементи даних називаються вершинами або вузлами. На зображенні вище A, B, C, D і E є вершинами. |
| Край (дуга) | Сполучні ланки між двома вузлами або вершинами називають ребром (дугою). Він має два кінці і представлений як (startingVertex, endingVertex). |
| Ненаправлений край | Це двонаправлений край. |
| Спрямований край | Це односпрямований край. |
| Зважений край | Край із значенням на ньому. |
| Ступінь | У Graph кількість ребер, з’єднаних з вершиною, називається ступенем. |
| Indegree | Загальна кількість вхідних ребер, з’єднаних з вершиною. |
| Попередня ступінь | Загальна кількість вихідних ребер, з’єднаних з вершиною. |
| Автопетля | Ребро називається автопетлею, якщо два його кінці збігаються. |
| Суміжність | Вершини називаються суміжними, якщо ребро з’єднане. |
Типи графів у структурі даних
Ось список найпоширеніших типи графів у структурі даних:
- Орієнтований граф
- Неорієнтований графік
- Зважений графік
- Двонаправлений графік
- Нескінченний графік
- Нульовий графік
- Тривіальний граф
- Мультиграф
- Повний графік
- Підключений граф
- Циклічний графік
- Спрямований ациклічний графік (DAG)
- Графік циклу
- Дводольний граф
- Графік Ейлера
- Графік Гамільтона
Застосування структури даних графа
Граф має багато варіантів використання. Існує багато алгоритмів, які часто використовують графіки. Ось деякі з застосувань Graph:
- Google Maps використовує графіки, щоб знайти перехрестя двох доріг і обчислити відстань між двома місцями.
Наприклад, Дейкстра, щоб знайти найкоротшу відстань між джерелом і пунктом призначення. - Facebook використовує Graphs, щоб знайти спільного друга користувачів. Його алгоритм розглядає кожного користувача як вузол графа.
- Для розподілу ресурсів використовується DAG (Direct Acyclic Graph). Він перевіряє залежність ресурсів.
- Пошукова система Google використовує графіки для створення рейтингу веб-сайтів.
- Пристрій відображення використовує структуру даних графа.
- маршрутизатор і протокол t використовує Graph, щоб дізнатися шлях призначення.
