Зміст

• Порівняльна діаграма
• Визначення Дерева
• Властивості дерева:
• Визначення графіка
• Властивості графіка:
• Висновок

Дерево та графік підпадають під категорію нелінійної структури даних, де дерево пропонує дуже корисний спосіб представлення зв’язку між вузлами в ієрархічній структурі, а графік слід за мережевою моделлю. Дерево та графік диференціюються тим, що структура дерева повинна бути з'єднана і ніколи не може мати циклів, тоді як у графі немає таких обмежень.

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

1. 1. Порівняльна діаграма
   2. Визначення
   3. Ключові відмінності
   4. Висновок

Порівняльна діаграма

Основа для порівняння	Дерево	Графік
Шлях	Лише одна між двома вершинами.	Дозволено більше одного шляху.
Кореневий вузол	Він має рівно один кореневий вузол.	Графік не має кореневого вузла.
Петлі	Не допускається циклів.	Графік може мати петлі.
Складність	Менш складний	Більш складний порівняно
Техніка обходу	Попереднє замовлення, замовлення та замовлення.	Перший пошук і пошук на глибині.
Кількість ребер	n-1 (де n - кількість вузлів)	Не визначено
Тип моделі	Ієрархічна	Мережа

Визначення Дерева

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

Існує кілька типів дерев, таких як двійкове дерево, двійкове дерево пошуку, дерево AVL, бінарне різьбове дерево, B-дерево тощо. Стиснення даних, зберігання файлів, маніпулювання арифметичним виразом та ігрові дерева - це деякі програми дерева структура даних.

Властивості дерева:

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

Існують різні терміни, пов’язані з деревами, такі як кінцевий вузол, край, рівень, ступінь, глибина, ліс тощо. Серед цих термінів деякі з них описані нижче.

• Край - Лінія, яка з'єднує два вузли.
• Рівень - Дерево розподіляється на рівні таким чином, що кореневий вузол знаходиться на рівні 0. Потім його безпосередні діти знаходяться на рівні 1, а його безпосередні діти знаходяться на рівні 2 і так далі до кінцевого або листового вузла.
• Ступінь - Це кількість підрядів вузла в даному дереві.
• Глибина - Це максимальний рівень будь-якого вузла в даному дереві і також відомий як висота.
• Термінальний вузол - Вузол вищого рівня - це кінцевий вузол, тоді як інші вузли, крім термінального та кореневого, відомі як нетермінальні вузли.

Визначення графіка

А графік це також математична нелінійна структура даних, яка може представляти різні види фізичної структури. Він складається з групи вершин (або вузлів) та набору ребер, що з'єднують дві вершини. Вершини на графіку представлені у вигляді точки або кіл, а ребра відображаються у вигляді сегментів дуги або лінії. Ребро представлено E (v, w), де v і w - пари вершин. Видалення ребра з контуру або підключеного графіка створює підграф, який є деревом.

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

Властивості графіка:

• Вершина в графі може бути з'єднана з будь-якою кількістю інших вершин за допомогою ребер.
• Край може бути двонаправлений або спрямований.
• Край можна зважити.

У графіку ми також використовуємо різні терміни, такі як сусідні вершини, шлях, цикл, ступінь, пов'язаний графік, повний графік, зважений графік тощо. Давайте розберемося з деякими з цих термінів.

• Суміжні вершини - Вершина a примикає до вершини b, якщо є край (a, b) або (b, a).
• Шлях - Шлях від випадкової вершини w - сусідня послідовність вершин.
• Цикл - Це шлях, де перша і остання вершини однакові.
• Ступінь - Це ряд ребер, що падають на вершину.
• Підключений графік - Якщо існує шлях від випадкової вершини до будь-якої іншої вершини, то цей графік відомий як пов'язаний графік.

1. У дереві існує лише один шлях між будь-якими двома вершинами, тоді як графік може мати односпрямований і двонаправлений шлях між вузлами.
2. У дереві рівно один кореневий вузол, і кожна дитина може мати лише одного батька. На противагу, у графіку немає поняття кореневого вузла.
3. Дерево не може мати циклів і самосмикань, тоді як графік може мати петлі та самоклітки.
4. Графіки є складнішими, оскільки вони можуть мати петлі та самокрутки. Навпаки, дерева прості порівняно з графіком.
5. Дерево обробляється методами попереднього замовлення, замовлення та після замовлення. З іншого боку, для обходу графів ми використовуємо BFS (перший пошук ширини) та DFS (глибинний перший пошук).
6. Дерево може мати n-1 краї. Навпаки, у графіку немає заздалегідь заданої кількості ребер, і це залежить від графіка.
7. Дерево має ієрархічну структуру, тоді як графік має мережеву модель.

Висновок

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