У попередньому відео ми розглянули абстрактну модель та базову імплементацію Бінарного Дерева Пошуку. Сьогодні ми розглянемо крайню структуру даних, яка дуже важлива у комп'ютерних системах Граф / Graph. Також казав, що в цьому відео буде весело - а чому розповім незабаром.
Тож погнали! В нас вже є розуміння про лінійні (Лист, Стек, Черга) та ієрархічні (Дерева) структури даних - все це лише засоби організації та зберігання даних для подальшої ефективної роботи з ними.
Граф - це також ієрархічна структура, яка складається з Вузлів / Nodes та Ребер / Edges, причому на відміну від дерева, Вузли можуть бути з'єднані в довільному порядку без обмежень.
Тобто виходить наступний цікавий факт - що Дерево це лише спеціальний тип Графу.
! Можливо Граф це теж лише особливий випадок іншої більш абстрактної структури, але наразі людству це невідомо.
З математики вам може бути відома математична модель теорії Графів:
Граф G - це впорядкована пара наборів множин V (Вершин / Vertices) та наборів E (Ребер / Edges). Більш детальна теорія https://uk.wikipedia.org/wiki/Теорія_графів
G = (V, E)
Наприклад візьмемо Граф:
Множина Вершин V буде дорівнювати = {A, B, C, D, E, F}
Множина Ребер E = {e1, e2, e3, e4, e5, e6, e7, e8}
Ребро також може бути Направленим / Directed та Ненаправленими / Undirected, як і сам Граф
Для такого випадку набір вершин V = {V1, V2, V3} , а ось набір зв'язків для вершин ми можемо записати як:
Для Ненаправленого Графу ребра (Figure 1) E = { {V1, V2}, {V2, V3}, {V1, V3} }
Для Направленого Графу ребра (Figure 1) E = { (V1, V2), (V2, V3), (V1, V3) }
Щоб краще зрозуміти Направлений Граф, ми можемо уявити собі місто з вулицями - односторонніми та двосторонніми дорогами.
Іншим прикладом Ненаправленого Графа є комп'ютерні інтернет мережі / Веб / World Wide Web / WWW:
Або ж соціальні мережі:
Цікава задачка яку вирішує для нас Facebook, рекомендація друзів (знайти Вузли які мають спільні Вузли, але не є з'єднаними) - це одна з класичних задач теорії графів.
Мапа швидкісних доріг між містами / Intercity:
На цьому прикладі ми можемо розглянути Незважений / Unweighted Граф, де всі Ребра рівнозначні. Та Зважений / Weighted Граф, де є вага Ребра. Тобто одні дороги з мапи швидше або кращі за інші.
Тобто наступну класичну проблему Графів, яку вирішує для нас Google maps - знайти найкращий маршрут від точки A до точки B.
Також Граф може мати Петлю на себе / Self-loop та Багатогранне / Multiedge Ребро
Наприклад якщо ми розглянемо Веб сторінки в інтернеті - як Вершини графу, то сторінка може посилатися сама на себе - це Петля.
Або ж якщо ми розглянемо мапу авіасполучень по світу - то ми побачимо що з одного міста в інше можна добратись кількома різними авіакомпаніями - тобто це і є Багатогранність.
Якщо цих ускладнень немає - то граф називають Простим / Simple. Надалі, під час реалізації алгоритмів, ми будемо мати на увазі саме такий Граф.
Цікаво що для Простого Графу ми можемо легко розрахувати максимальне число Ребер.
Якщо ми маємо n = |V| Вершин , тоді число Ребер знаходиться в діапазоні
0 <= |E| <= n * (n-1) для Направленого / Directed Графу
0 <= |E| <= n * (n-1) / 2 для Ненаправленого / Undirected Графу, тому що ми маємо тільки одне Ребро між Вершинами.
В залежності від числа Ребер Графи бувають:
Щільні / Dense -> дуже багато Ребер
Розріджені / Sparse -> дуже мало Ребер
Тому дуже важливо розуміти з якими даними ми будемо працювати, тобто який саме буде Граф Щільний чи Розріджений. Від цього залежить яку структуру використовувати для ефективного зберігання цих даних(Ребер, Вершин) та роботи алгоритмів. Для Щільних графів доцільно використовувати Матрицю (масив масивів) наприклад, для Розріджених - це може бути Списки, як варіант.
Наступне що нам треба знати для роботи з Графом, що таке Шлях / Path - а це послідовність об'єднаних Ребрами Вершин. Ми можемо мати багато варіантів як пройти наприклад від A до С. Наприклад шляхи <A, C> ; <A, B, C>; <A, B, E, D, C> і тд.
Якщо шлях не має повторів Вершин - це Простий шлях / Simple Path.
Приклад шляху від A до С з повторами - <A, F, D, E, F, A, C>
Залишу також посилання на більш детальну теорію для Графів під відео, кому цікаво.
А ми поки підемо далі, та на базі цих знань визначимо абстрактну модель для простого Графу - це структура даних яка може:
- Зберігати дані у формі Вершин (Вузлів) та Ребер (Посилань/ Зв'язків)
- Додавати Вершини та Ребра
- Видаляти Вершини та Ребра
- Читати та оновлювати дані з Вершин (та Ребер, якщо Зважений Граф)
- Перевіряти чи дві Вершини є суміжні, тобто мають спільне Ребро (з'єднані)
- Повертати сусідні Вершини, тобто всі вершини які мають суміжне Ребро з заданою Вершиною
Перейдемо до специфікації та імплементації.
Визначимо специфікацію абстрактної моделі для структури даних Simple Graph / Простий Граф:
Імплементація для структури даних Simple Graph / Простий Граф:
Git репозиторій https://github.com/kostrub-online/Computer-Science
Замість висновку
Тепер ви маєте в своєму наборі швейцарський ніж зі структурами даних на різні випадки.
З цими знаннями ви можете легко вирішувати складні задачі та проблеми. А також проєктувати ефективні системи.
Ось чому я казав, що буде весело. Тому що всі ці скіли значно допоможуть вам пройти на 5 веселих букв: FAANG
Це супер інвестиція вашого часу в своє майбутнє. Нехай щастить з цим! Пишіть рекрутерам, качайте скіли та профайл, питайте реферал - і все вийде!
На цьому в мене все для вас на тему Структури даних та базові алгоритми. Якщо будуть запити можливо зроблю ще курси. Пишіть що б вам могло бути цікаво: технології чи системний дизайн, тощо. Далі більше! На зв'язку.
0 Коментарі