Типи графів у структурі даних з прикладами
Сара Чен
⚡ Розумний підсумок
Графи в структурах даних — це нелінійні колекції вершин і ребер, класифіковані на сімейства, такі як орієнтовані, неорієнтовані, зважені, циклічні, ациклічні, повні, зв'язані, двочасткові, графи Ейлера та Гамільтона на основі структури.
Граф — це нелінійна структура даних, що складається з вершин і ребер. Вершини містять інформацію або дані, а ребра виконують роль сполучної ланки між парою вершин.
Графи можуть бути кількох типів, залежно від положення вузлів та ребер. Ось деякі важливі типи графів:
Орієнтований граф
Ребра орієнтованого графа містять стрілки, що позначають напрямок. Стрілка визначає, куди вказує або де закінчується ребро. Ось приклад орієнтованого графа.
Орієнтований граф
- Ми можемо перейти від вузла A до D.
- Однак, ми не можемо перейти від вузла D до вузла A, оскільки ребро вказує від A до D.
- Оскільки граф не має вагових коефіцієнтів, подорож від вершини A до D коштуватиме так само, як подорож від D до F.
Неорієнтований графік
Неорієнтований граф містить ребра без вказівників. Це означає, що ми можемо переміщатися між двома вершинами у зворотному напрямку. Ось простий приклад неорієнтованого графа.
Неорієнтований графік
На наведеному вище графіку
- Ми можемо перейти з пункту А до пункту Б.
- Ми також можемо перейти з пункту B до пункту A.
- Ребра не містять напрямків.
Це приклад неорієнтованого графа, що має скінченну кількість вершин і ребер без ваг.
Зважений графік
Граф, що містить ваги або витрати на ребрах, називається зваженим графом. Числове значення зазвичай представляє вартість переміщення з однієї вершини в іншу. Як орієнтовані, так і неорієнтовані графи можуть мати ваги на своїх ребрах. Ось приклад зваженого графа (орієнтованого).
Орієнтований граф з вагою
- З пункту А до пункту Б є ребро, а вага дорівнює 5, що означає, що переміщення з пункту А до пункту Б коштуватиме нам 5.
- А вказує на B, але на цьому графіку B не має прямої переваги над A. Отже, ми не можемо подорожувати з B до A.
- Однак, якщо ми хочемо перейти від A до F, існує кілька шляхів. Шляхи - ADF та ABF. ADF коштуватиме (10+11) або 21.
- Тут шлях ABF коштуватиме (5+15) або 20. Тут ми додаємо вагу кожного ребра в шляху.
Ось приклад неорієнтованого графа з вагами:
Неорієнтований граф з вагою
Тут край має вагу, але не має напрямку. Отже, це означає, що подорож від вершини A до D коштуватиме 10 і навпаки.
Двонаправлений графік
Двонаправлені та неорієнтовані графи мають спільну властивість, а саме:
- Зазвичай, неорієнтований граф може мати одне ребро між двома вершинами.
Наприклад:
- Тут перехід від A до D або D до A коштуватиме 10.
- У двонаправленому графі ми можемо мати два ребра між двома вершинами.
Ось приклад:
Двонаправлений графік
Подорож з A до D коштуватиме нам 17, але подорож з D до A коштуватиме нам 12. Отже, ми не можемо призначити дві різні ваги, якщо це неорієнтований граф.
Нескінченний графік
Граф міститиме нескінченну кількість ребер та вузлів. Якщо граф нескінченний і водночас зв'язний, то він також міститиме нескінченну кількість ребер. Тут розширені ребра означають, що більше ребер можуть бути з'єднані з цими вузлами через ребра. Ось приклад нескінченного графа:
Нескінченний графік
Нульовий графік
Нульовий граф містить лише вузли або вершини, але не має ребер. Якщо задано граф G = (V, E), де V – вершини, а E – ребра, він буде нульовим, якщо кількість ребер E дорівнює нулю. Ось приклад нульового графа:
Нульовий графік
Тривіальний граф
Структура даних графа вважається тривіальною, якщо присутня лише одна вершина або вузол без ребер. Ось приклад тривіального графа:
Мультиграф
Граф називається мультиграфом, коли між двома вершинами присутні кілька ребер або вершина має петлю. Термін «петля» в структурі даних графа означає ребро, що вказує на той самий вузол або вершину. Мультиграф може бути орієнтованим або неорієнтованим. Ось приклад мультиграфа:
З B до A ведуть два ребра. Більше того, вершина E має петлю в собі. Наведений вище графік є орієнтованим графом без ваг на ребрах.
Повний графік
Граф вважається повним, якщо кожна вершина має спрямовані або неорієнтовані ребра з усіма іншими вершинами. Припустимо, що загалом V вершин, і кожна вершина має рівно V-1 ребер. Тоді такий граф називатиметься повним графом. У цьому типі графа кожна вершина з'єднана з усіма іншими вершинами через ребра. Ось приклад повного графа з п'ятьма вершинами:
На зображенні видно, що загальна кількість вузлів дорівнює п'яти, і всі вузли мають рівно чотири ребра.
Підключений граф
Граф називається зв'язним, якщо ми починаємо з вузла або вершини і можемо перейти до всіх вузлів з початкового вузла. Для цього між кожною парою вузлів або вершин має бути принаймні одне ребро. Ось приклад зв'язного графа:
Ось деякі пояснення вищезгаданого зв'язаного графа:
- Якщо припустити, що між C та F немає ребра, ми не можемо перейти з A до G. Однак ребро C до F дозволяє нам перейти до будь-якого вузла з заданого вузла.
- Повний граф є зв’язаним графом, оскільки ми можемо переходити від вузла до будь-якого іншого вузла в даному графіку.
Циклічний графік
Граф називається циклічним, якщо в ньому присутній один або декілька циклів. Ось приклад циклічного графа:
Тут вершини A, B та C утворюють цикл. Граф може мати кілька циклів усередині себе.
Спрямований ациклічний графік (DAG)
Граф називається орієнтованим ациклічним графом або DAG, якщо всередині графа немає циклів. DAG важливий під час виконання Топологічне сортування або знаходження порядку виконання. DAG також важливий для створення систем планування або сканування залежностей ресурсів тощо. Однак, наведений вище графік не містить жодного циклу всередині. Ось простий приклад орієнтованого ациклічного графа (DAG):
Графік циклу
Циклічний граф — це не те саме, що циклічний граф. У циклічному графі кожен вузол матиме рівно два з'єднані ребра, тобто кожен вузол матиме рівно два ступені. Ось приклад циклічного графа:
Дводольний граф
Ці види діаграми є спеціальними видами графів, де вершини призначаються двом множинам. Двочастковий граф повинен дотримуватися правила:
- Два набори вершин повинні бути різними, що означає, що всі вершини необхідно розділити на дві групи або набори.
- Вершини з однакової множини не повинні утворювати жодних ребер.
Графік Ейлера
Структура даних Graph вважається графом Ейлера, якщо всі вершини мають парний степінь. Термін "степінь вершин" означає кількість ребер, що вказують на певну вершину або виходять з неї. Ось приклад графа Ейлера:
Усі вершини мають парні ступені. Вершини A, D, E та H мають два ступені. Тут вузол C має чотири ступені, що є парним.
Графік Гамільтона
Граф Гамільтона — це зв'язний граф, де можна відвідати всі вершини з заданої вершини, не повертаючись до того самого вузла чи використовуючи те саме ребро. Такий тип зв'язного графа відомий як «граф Гамільтона». Шлях, який ви проходите, щоб перевірити, чи є даний граф графом Гамільтона, називається гамільтоновим шляхом. Ось простий приклад графа Гамільтона:
На цьому зображенні ми можемо відвідати всі вершини з будь-якого вузла на наведеному вище графіку. Одним із шляхів може бути ADCHBEТакож можливо знайти цикл Гамільтона. Цикл Гамільтона починається та закінчується в одній вершині. Отже, цикл Гамільтона буде АДЧБЕА.
