Різниця між графіком і деревом

Графік проти дерева

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

Графік

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

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

Інший спосіб зробити це - зберегти двовимірний масив або матрицю M, що має булеві значення. Існування краю від вузла i до j визначається введенням Mij. Однією з переваг цього методу є з’ясування наявності між двома вузлами ребра.

Дерево

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

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

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