Нелінійна структура даних складається з набору елементів, які розподілені по площині, що означає, що не існує такої послідовності між елементами, як вона існує в лінійній структурі даних.
Діаграма порівняння
| Основа для порівняння | Дерево | Графік |
|---|---|---|
| Шлях | Тільки один між двома вершинами. | Дозволено більше одного шляху. |
| Кореневий вузол | Він має точно один кореневий вузол. | Графік не має кореневого вузла. |
| Петлі | Жодні петлі не допускаються. | Графік може мати петлі. |
| Складність | Менш складний | Більш складний порівняно |
| Методи обходу | Попереднє замовлення, замовлення та замовлення. | Перший пошук по глибині і пошук по глибині. |
| Кількість країв | n-1 (де n - кількість вузлів) | Не визначений |
| Тип моделі | Ієрархічна | Мережа |
Визначення дерева
Дерево - це кінцева колекція елементів даних, які зазвичай називаються вузлами. Як зазначалося вище, дерево є нелінійною структурою даних, яка упорядковує елементи даних у відсортованому порядку. Він використовується, щоб показати ієрархічну структуру між різними елементами даних і організовує дані в гілки, які пов'язують інформацію. Додавання нового ребра в дереві призводить до утворення циклу або контуру.
Існує декілька типів дерев, таких як двійкове дерево, дерево бінарного пошуку, дерево AVL, бінарна деревина, B-дерево і т.д. Стиснення даних, зберігання файлів, маніпулювання арифметичним виразом і деревами ігор є деякими з застосувань дерева структура даних.
Властивості дерева:
- У верхній частині дерева, що називається коренем дерева, є призначений вузол.
- Інші елементи даних поділяються на непересічні підмножини, які називаються піддеревом.
- Дерево розширюється у висоту в бік дна.
- Дерево має бути підключеним, що означає, що має бути шлях від одного кореня до всіх інших вузлів.
- Вона не містить жодних петель.
- Дерево має n-1 ребер.
Існують різні терміни, пов'язані з деревами, такими як кінцевий вузол, край, рівень, ступінь, глибина, ліс і т.д. Серед цих термінів деякі з них описані нижче.
- Edge - лінія, яка з'єднує два вузли.
- Рівень - Дерево поділяється на рівні таким чином, що кореневий вузол знаходиться на рівні 0. Тоді його безпосередні діти знаходяться на рівні 1, і його безпосередні діти знаходяться на рівні 2 і так далі до терміналу або листового вузла.
- Ступінь - це кількість піддерев вузла в даному дереві.
- Глибина - це максимальний рівень будь-якого вузла в даному дереві, також відомий як висота .
- Термінальний вузол - вузол найвищого рівня - це термінальний вузол, в той час як інші вузли, крім термінального і кореневого вузлів, відомі як нетермінальні вузли.
Визначення графіка
Граф - це також математична нелінійна структура даних, яка може представляти різні види фізичної структури. Він складається з групи вершин (або вузлів) і множини ребер, які з'єднують дві вершини. Вершини на графіку представлені у вигляді точок або кіл, а ребра показані як дуги або відрізки. Ребро представлено за допомогою E (v, w) де v і w є парами вершин. Видалення краю з схеми або пов'язаного графіка створює підграф, який є деревом.
Графіки поділяються на різні категорії, такі як спрямований, ненаправлений, пов'язаний, не пов'язаний, простий і мультиграфовий. Комп'ютерна мережа, транспортна система, графік соціальних мереж, електричні схеми та проектування є деякими з застосувань структури даних графіків. Вона також застосовується в техніці управління, яка називається PERT (методика оцінки та аналізу програм) і CPM (метод критичного шляху), в якому аналізується структура графіка.
Властивості графіка:
- Вершина в графі може бути з'єднана з будь-яким числом інших вершин за допомогою ребер.
- Край може бути двонаправленим або спрямованим.
- Край можна зважити.
У графі також використовуються різні терміни, такі як суміжні вершини, шлях, цикл, ступінь, пов'язаний графік, повний граф, зважений графік і т.д. Давайте зрозуміємо деякі з цих термінів.
- Суміжні вершини - Вершина a є суміжною з вершиною b, якщо є ребро (a, b) або (b, a).
- Шлях - Шлях від випадкової вершини w є суміжною послідовністю вершин.
- Цикл - це шлях, де перша і остання вершини однакові.
- Ступінь - це число ребер, що падають на вершину.
- Зв'язаний графік - Якщо існує шлях від випадкової вершини до будь-якої іншої вершини, то цей графік відомий як пов'язаний графік.
Ключові відмінності між деревом і графіком
- У дереві існує тільки один шлях між будь-якими двома вершинами, тоді як графік може мати односпрямовані і двонаправлені шляхи між вузлами.
- У дереві є рівно один кореневий вузол, і кожна дитина може мати тільки одного батька. На відміну від, в графі, немає поняття кореневого вузла.
- Дерево не може мати петель і самообіг, а граф може мати петлі і самоцикли.
- Графи більш складні, оскільки можуть мати петлі та самообмеження. На противагу цьому, дерева є простими порівняно з графіком.
- Дерево проходить за допомогою методів попереднього замовлення, в порядку і після замовлення. З іншого боку, для обходу графів ми використовуємо BFS (пошук по ширині) і DFS (перший пошук глибини).
- Дерево може мати n-1 ребер. Навпаки, на графіку немає попередньо визначеного числа ребер, і це залежить від графіка.
- Дерево має ієрархічну структуру, тоді як граф має мережеву модель.
Висновок
Графік і дерево - це нелінійна структура даних, яка використовується для вирішення різних складних задач. Граф - це група вершин і ребер, де ребро з'єднує пару вершин, тоді як дерево розглядається як мінімально пов'язаний граф, який повинен бути з'єднаний і вільний від петель.
