Содержание

• Сравнительная таблица
• Определение дерева
• Свойства дерева:
• Определение графика
• Свойства графика:
• Заключение

Дерево и граф относятся к категории нелинейных структур данных, где дерево предлагает очень полезный способ представления отношений между узлами в иерархической структуре, а граф следует сетевой модели. Дерево и граф различаются тем, что древовидная структура должна быть соединена и не может иметь петель, в то время как в графе таких ограничений нет.

Нелинейная структура данных состоит из набора элементов, которые распределены на плоскости, что означает, что между элементами нет такой последовательности, как в линейной структуре данных.

1. 1. Сравнительная таблица
   2. Определение
   3. Ключевые отличия
   4. Заключение

Сравнительная таблица

Основа для сравнения	дерево	график
Дорожка	Только один между двумя вершинами.	Допускается более одного пути.
Корневой узел	У него ровно один корневой узел.	График не имеет корневого узла.
Loops	Петли не допускаются.	График может иметь петли.
сложность	Менее сложный	Более сложный сравнительно
Методы обхода	Предварительный заказ, заказ и заказ.	Поиск в ширину и поиск в глубину.
Количество ребер	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. Дерево имеет иерархическую структуру, тогда как граф имеет сетевую модель.

Заключение

График и дерево представляют собой нелинейную структуру данных, которая используется для решения различных сложных задач. Граф - это группа вершин и ребер, где ребро соединяет пару вершин, тогда как дерево рассматривается как минимально связанный граф, который должен быть связным и свободным от петель.