✅ Графік структури даних - Вивчіть термінології та основні операції

Вступ до графіку в структурі даних

Вступ до графіку в структурі даних

Графіки - це нелінійні структури даних, що містять кінцевий набір вузлів і ребер. Вузли - це елементи, а краї упорядковані парами з'єднань між вузлами.

Зауважте слово нелінійне. Нелінійна структура даних - це структура, де елементи не розташовані в послідовному порядку. Наприклад, масив - це лінійна структура даних, оскільки елементи розташовані один за одним. Ви можете пройти всі елементи масиву за один пробіг. Такого не буває з нелінійними структурами даних. Елементи нелінійної структури даних розташовані в декількох рівнях, часто за ієрархічною схемою. Графіки нелінійні.

Наступне слово, на яке слід звернути увагу, - кінцеве. Графік визначаємо так, щоб він мав кінцеву і підрахункову кількість вузлів. Це досить не погоджений термін. По суті, Графік може мати нескінченну кількість вузлів і все ще бути кінцевим. Наприклад, родинне дерево починаючи від Адама та Єви. Це відносно нескінченний графік, але все ще піддається обліку і тому вважається кінцевим.

Приклад реального світу

Найкращий приклад графіків у реальному світі - Facebook. Кожна людина у Facebook - це вузол і з'єднаний через краї. А - друг Б. Б - друг С і так далі.

Термінології

Тут наведені нижче терміни графіків у структурі даних

1. Представлення графіка: Зазвичай графік представлений у вигляді пари множин (V, E). V - сукупність вершин або вузлів. Е - сукупність країв. У наведеному вище прикладі
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)

2. Вузол або вершина: елементи графіка з'єднані через ребра.

3. Краї: шлях або лінія між двома вершинами в графі.

4. Суміжні вузли: Два вузли називаються суміжними, якщо вони з'єднані через край. У наведеному вище прикладі вузол A суміжний з вузлами B, C і D, але не до вузла E.

5. Шлях: Шлях - це послідовність ребер між двома вузлами. По суті це обхід, що починається на одному вузлі і закінчується на іншому. У наведеному вище прикладі є кілька шляхів від вузла A до вузла E.

Шлях (A, E) = (AB, BE)
АБО
Шлях (A, E) = (AC, CD, DE)
АБО
Шлях (A, E) = (AD, DE)

6. Ненаправлений графік: Непрямий графік - це той, де краї не визначають конкретного напрямку. Краї двосторонні.

Приклад

Таким чином, у цьому прикладі ребро змінного струму може проходити як від А до С, так і від С до А. Подібно до всіх ребер. Шлях від вузла B до вузла C буде або (BA, AC) або (BD, DC).

7. Направлений графік: спрямований графік - це той, де краї можуть проходити лише у визначеному напрямку.

Приклад

Таким чином, у тому ж прикладі тепер ребра направлені. Можна лише пройти край уздовж його напрямку. Зараз немає шляху від вузла B до вузла C.

8. Зважений графік: зважений графік - це той, де краї пов'язані з вагою. Це, як правило, вартість переходу краю.

Приклад

Таким чином, у тому ж прикладі тепер краї мають певну вагу, пов’язану з ними. Існує два можливі шляхи між вузлом А до вузла Е.
Шлях1 = (AB, BD, DE), вага1 = 3 + 2 + 5 = 10
Шлях2 = (AC, CD, DE), Вага2 = 1 + 3 + 5 = 9
Зрозуміло, що віддати перевагу Path2, якщо метою є досягнення вузла E від вузла A з мінімальними витратами.

Основні операції на графіку

Нижче наведено базові операції графіка

1. Додати / видалити вершину

Це найпростіша операція на графіку. Ви просто додаєте вершину до графіка. Він не повинен бути з'єднаний з будь-якою іншою вершиною через край. Видаляючи вершину, ви повинні видалити всі краї, що починаються від і закінчуються на видаленій вершині.

2. Додати / видалити край

Ця операція додає або видаляє край між двома вершинами. Коли всі ребра, що починаються від вершини і закінчуються на вершині, видаляються, вершина стає ізольованою вершиною.

3. Перший пошук за шириною (BFS)

Це обхідна операція на графіку. BFS горизонтально перетинає графік. Це означає, що він проходить всі вузли на одному рівні, перш ніж перейти до наступного рівня.
Алгоритм BFS починається у верхній частині першого вузла графіка, а потім проходить усі сусідні вузли до нього. Після проходження всіх сусідніх вузлів алгоритм повторює ту саму процедуру для дочірніх вузлів.

Приклад

Перехід вищевказаного графіка способом BFS призведе до A -> B -> C -> D -> E -> F -> G. Алгоритм починається з вузла A і обходить усі його суміжні вузли B, C і D. всі чотири вузли як відвідані. Після проходження всіх сусідніх вузлів A алгоритм переміщується до першого сусіднього вузла А та повторює ту саму процедуру. У цьому випадку вузол є B, а сусідні вузли до B - E та F. Далі сусідні вузли до C проходять. Після відвідування всіх вузлів операція закінчується.

4. Поглиблений перший пошук (DFS)

По глибині Перший пошук або DFS перетинає графік вертикально. Він починається з кореневого вузла або першого вузла графіка і обходить всі дочірні вузли перед тим, як перейти до сусідніх вузлів.

Приклад

Переміщення вищевказаного графіка способом BFS призведе до A -> B -> E -> F -> C -> G -> D. Алгоритм починається з вузла A і обходить усі його дочірні вузли. Як тільки він стикається з B, здається, що у нього є додаткові дочірні вузли. Отже, дочірні вузли B проходять перед тим, як перейти до наступного дочірнього вузла А.

Реалізація графіків у реальному світі

Проектування електричних схем для передачі електроенергії.
Проектування мережі взаємопов'язаних комп'ютерів.
Вивчення молекулярної, хімічної та клітинної структури будь-якої речовини, наприклад ДНК людини.
Проектування транспортних маршрутів між містами та місцями в межах міста.

Висновок - Графік структури даних

Графіки - дуже корисна концепція в структурах даних. Він має практичну реалізацію майже в кожній галузі. Дуже важливо зрозуміти основи теорії графів, виробити розуміння алгоритмів структури графа.
Ця стаття була лише вступом до графіків. Це просто трамплін. Рекомендується глибше зануритися в тему теорії графів.

Графік структури даних - Вивчіть термінології та основні операції