Нелинейная структура данных состоит из набора элементов, которые распределены на плоскости, что означает, что между элементами нет такой последовательности, как в линейной структуре данных.
Сравнительная таблица
| Основа для сравнения | дерево | график |
|---|---|---|
| Дорожка | Только один между двумя вершинами. | Допускается более одного пути. |
| Корневой узел | У него ровно один корневой узел. | Граф не имеет корневого узла. |
| 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 является смежной последовательностью вершин.
- Цикл - это путь, в котором первая и последняя вершины совпадают.
- Степень - это число ребер, падающих на вершину.
- Связный граф. Если существует путь от случайной вершины до любой другой вершины, то этот граф называется связным графом.
Ключевые различия между деревом и графиком
- В дереве существует только один путь между любыми двумя вершинами, тогда как граф может иметь однонаправленные и двунаправленные пути между узлами.
- В дереве есть ровно один корневой узел, и у каждого дочернего элемента может быть только один родительский узел. В отличие от этого, в графе отсутствует понятие корневого узла.
- У дерева не может быть циклов и автопетлей, в то время как в графе могут быть циклы и автопетли.
- Графики более сложны, так как могут иметь циклы и циклы. Деревья, напротив, просты по сравнению с графиком.
- Дерево пересекается с использованием методов предварительного заказа, по порядку и после заказа. С другой стороны, для обхода графа мы используем BFS (поиск по ширине) и DFS (поиск по глубине).
- Дерево может иметь n-1 ребер. Наоборот, в графе нет заранее определенного числа ребер, и это зависит от графа.
- Дерево имеет иерархическую структуру, тогда как граф имеет сетевую модель.
Заключение
График и дерево представляют собой нелинейную структуру данных, которая используется для решения различных сложных задач. Граф - это группа вершин и ребер, где ребро соединяет пару вершин, тогда как дерево рассматривается как минимально связанный граф, который должен быть связным и свободным от петель.
