В чем разница между структурой данных Tree и Graph?
С академической точки зрения, в чем принципиальная разница между структурой данных Tree и Graph? А как насчет поиска по дереву и по графику?
13 ответов
Дерево - это ограниченная форма Графа.
Деревья имеют направление (родительские / дочерние отношения) и не содержат циклов. Они вписываются в категорию направленных ациклических графов (или DAG). Таким образом, деревья - это группы доступности базы данных с ограничением на то, что у ребенка может быть только один родитель.
Важно отметить, что деревья - это не рекурсивная структура данных. Они не могут быть реализованы как рекурсивная структура данных из-за вышеуказанных ограничений. Но любая реализация DAG, которая обычно не является рекурсивной, также может быть использована. Моя предпочтительная реализация Tree представляет собой централизованное представление карты и не является рекурсивной.
Графики - это, как правило, поисковое дыхание в первую очередь или в глубину. То же самое относится и к дереву.
Вместо объяснения я предпочитаю показывать это в картинках.
Дерево в реальном времени
График в реальной жизни
Да, карту можно визуализировать как структуру данных графа.
Увидев их, как это делает жизнь проще. Деревья используются в тех местах, где мы знаем, что у каждого узла есть только один родитель. Но у графов может быть несколько предшественников (термин родитель обычно не используется для графов).
В реальном мире вы можете представлять практически все, используя графики. Я использовал карту, например. Если вы рассматриваете каждый город как узел, до него можно добраться из нескольких точек. Точки, которые ведут к этому узлу, называются предшественниками, а точки, к которым этот узел приведет, называются преемниками.
Электрическая схема, план дома, компьютерной сети или речной системы - еще несколько примеров графиков. Многие примеры из реального мира можно рассматривать как графики.
Техническая схема может быть такой
Дерево:
График:
Обязательно обратитесь по ссылкам ниже. Они ответят почти на все ваши вопросы о деревьях и графиках.
Рекомендации:
Другие ответы полезны, но в них отсутствуют свойства каждого из них:
График
Ненаправленный граф, источник изображения: Википедия
Направленный граф, источник изображения: Википедия
- Состоит из набора вершин (или узлов) и набора ребер, соединяющих некоторые или все из них.
- Любое ребро может соединить любые две вершины, которые еще не соединены одним и тем же ребром (в том же направлении, в случае ориентированного графа)
- Не обязательно быть связным (ребра не должны соединять все вершины вместе): один граф может состоять из нескольких несвязных наборов вершин
Может быть направленным или неориентированным (что применимо ко всем ребрам в графе)
Согласно Википедии:Например, если вершины представляют людей на вечеринке, и между двумя людьми есть ребро, если они пожимают руки, тогда этот граф неориентированный, потому что любой человек A может пожать руку человеку B, только если B также пожимает руку A. Напротив, если любое ребро от человека A до человека B соответствует A, восхищающемуся B, то этот граф является направленным, потому что восхищение не обязательно взаимное.
Дерево
Источник изображения: Википедия
- Тип графика
- Вершины чаще называют "узлами".
- Ребра направлены и представляют собой отношения "является дочерним элементом" (или "является родительским элементом").
- У каждого узла (кроме корневого) есть ровно один родитель (и ноль или более дочерних узлов)
- Имеет ровно один "корневой" узел (если в дереве есть хотя бы один узел), который является узлом без родителя.
- Должен быть подключен
- Является ациклическим, то есть не имеет циклов: "цикл - это путь [AKA последовательность] ребер и вершин, в котором вершина достижима из себя"
Вышеупомянутые свойства частично совпадают. В частности, последние два свойства подразумеваются остальными свойствами. Но все же стоит отметить их все.
TREE :
1. Only one path exist between two vertices (Nodes).
2. Root node is the starting node of the tree.
3. Tree doesn't have loops.
4. Number of edges: n-1 (where n is number of nodes)
5. Tree looks like Hierarchical
6. All trees are graph.
GRAPH :
1. More than one path is allowed between two vertices.
2. There is no root node concept (we can start from any node).
3. There can be loop in graph.
4. Number of edges are not defined.
5. Graph looks like Network.
6. All graphs are not tree.
Более подробное объяснение вы можете найти в этом видео -> https://www.youtube.com/watch?v=KVHrjVTp9_w
Дерево - это особая форма графа, то есть минимально связный граф, имеющий только один путь между любыми двумя вершинами.
В графе может быть более одного пути, т.е. граф может иметь однонаправленные или двунаправленные пути (ребра) между узлами
Также вы можете увидеть более подробную информацию: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/
Разница между графиком и древовидной структурой данных
деревья
Дерево - это особая форма графа, то есть минимально связный граф, имеющий только один путь между любыми двумя вершинами.
Дерево - это особый случай графа, в котором нет циклов, цепей и самоконтролей.
В дереве есть ровно один корневой узел, и у каждого ребенка есть только один родитель.
В деревьях есть родительские дочерние отношения, поэтому поток может быть там с направлением сверху вниз или наоборот.
5. Деревья являются менее сложными, чем графы, так как не имеют циклов, не имеют петель и все еще связаны.
6. Обход дерева - это особый случай обхода графа. Дерево перебирается в предзаказе, в порядке и после заказа (все три в алгоритме DFS или BFS)
7. В деревьях существует множество правил / ограничений для установления связей между узлами через ребра.
8. Деревья входят в категорию DAG: Направленные ациклические графы - это своего рода ориентированный граф, который не имеет циклов.
9. Различными типами деревьев являются: Двоичное дерево, Двоичное дерево поиска, AVL-дерево, Кучи.
10.Деревянные приложения: сортировка и поиск, такие как Tree Traversal & Binary Search.
11. Дерево всегда имеет n-1 ребер.
12. Дерево - это иерархическая модель.
диаграммы
В графе может быть более одного пути, т.е. граф может иметь однонаправленные или двунаправленные пути (ребра) между узлами
- График может иметь циклы, схемы, а также может иметь собственные циклы.
3. В графе нет такого понятия корневого узла.
4.В графике нет таких родительских дочерних отношений.
5. Графы являются более сложными по сравнению с деревьями, поскольку они могут иметь циклы, циклы и т. Д.
6. Граф проходит через DFS: поиск в глубину и в BFS: алгоритм поиска в ширину
7. В графах нет таких правил / ограничений для соединения узлов через ребра.
8. Граф может быть циклическим или ациклическим.
9.Heaps. Существует в основном два типа графов: ориентированные и неориентированные графы.
10. Графические приложения: раскраска карт в OR (PERT & CPM), алгоритмы, раскраска графика, планирование заданий и т. Д.
- В графе нет. ребер зависит от графа.
12. Граф - это модель сети.
Пример дерева:
График:
В дереве каждый узел имеет ровно один узел-предшественник, кроме корневого узла, и один или два узла-преемника. Это может быть пройдено с использованием обходов по порядку, предварительному заказу и после заказа. Дерево - это особый вид графа без цикла, который называется DAG(направленный ациклический граф). Дерево - это иерархическая модель.
В Graph каждый узел имеет один или несколько узлов-предшественников и узлов-преемников. График перемещается с использованием алгоритмов поиска в глубину (DFS) и Breath First Search (BFS). Граф имеет цикл, поэтому он сложнее дерева. График - это сетевая модель. Существует два вида графов: ориентированные графы и неориентированные графы.
Дерево - это в основном неориентированный граф, который не содержит цикла, поэтому мы можем сказать, что дерево является более ограниченной формой графа. Однако дерево и граф имеют разное применение для реализации различных алгоритмов программирования. Например, граф можно использовать для модели дорожной карты, а дерево можно использовать для реализации любой иерархической структуры данных.
Деревья очевидны: это рекурсивные структуры данных, состоящие из узлов с дочерними элементами.
Карта (он же словарь) - это пары ключ / значение. Дайте карте ключ, и он вернет соответствующее значение.
Карты могут быть реализованы с использованием деревьев, надеюсь, вас это не смущает.
ОБНОВЛЕНИЕ: Запутывание "графика" для "карты" очень запутанно.
Графики сложнее деревьев. Деревья подразумевают рекурсивные отношения между родителями и детьми. Существуют естественные способы обхода дерева: сначала глубина, ширина ширина, порядок уровней и т. Д.
Графы могут иметь однонаправленные или двунаправленные пути между узлами, быть циклическими или ациклическими и т. Д. Я считаю, что графы являются более сложными.
Я думаю, что беглый поиск в любом тексте приличных структур данных (например, "Руководство по разработке алгоритмов") даст больше и лучше информации, чем любое количество ответов SO. Я бы порекомендовал вам не идти по пассивному маршруту и начать делать некоторые исследования для себя.
Простая концепция состоит в том, что у Tree нет цикла и он однонаправлен, тогда как Graph формирует цикл, и он будет двунаправленным в некоторых случаях и однонаправленным в других.
Дерево - это орграф такой, что:
а) с удаленными направлениями ребер, он связан и ацикличен
- Вы можете удалить либо предположение, что оно является ациклическим
- Если оно конечно, вы можете альтернативно удалить предположение, что оно связано
б) каждая вершина, кроме одной, корня имеет степень 1
в) корень имеет степень 0
- Если существует только конечное число узлов, вы можете удалить либо предположение, что корень имеет степень 0, либо предположение, что узлы, отличные от корня, имеют степень 1.
Ссылка: http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf
Один корневой узел в дереве и только один родитель для одного потомка. Однако понятия корневого узла не существует. Другое отличие состоит в том, что дерево - это иерархическая модель, а граф - это сетевая модель.
В математике граф представляет собой представление множества объектов, где некоторые пары объектов связаны между собой ссылками. Взаимосвязанные объекты представлены математическими абстракциями, называемыми вершинами, а ссылки, соединяющие некоторые пары вершин, называются ребрами.[1] Как правило, график изображается в виде диаграммы в виде набора точек для вершин, соединенных линиями или кривыми для ребер. Графы являются одним из объектов изучения дискретной математики.