В чем разница между структурой данных Tree и Graph?

Дерево - это просто ограниченная форма графа.

Деревья имеют направление (отношения родитель / потомок) и не содержат циклов. Они подходят для категории направленных ациклических графов (или DAG). Итак, деревья - это группы доступности базы данных с ограничением, что у дочернего элемента может быть только один родитель.

Важно отметить одну вещь: деревья не являются рекурсивной структурой данных. Они не могут быть реализованы в виде рекурсивной структуры данных из-за указанных выше ограничений. Но также можно использовать любую реализацию DAG, которая обычно не является рекурсивной. Моя предпочтительная реализация Tree представляет собой централизованное представление карты и не является рекурсивным.

Графики обычно ищутся в ширину или в глубину. То же самое и с деревом.

Вместо того, чтобы объяснять, я предпочитаю показывать это в картинках.

Дерево в реальном времени

Использование графика в реальной жизни

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

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

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

электрическая принципиальная схема, план дома, компьютерная сеть или речная система - еще несколько примеров графиков. Многие примеры из реального мира можно рассматривать как графики.

Техническая схема может быть такой

Дерево:

График:

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

Использованная литература :

1. http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#_Toc362296541

2. http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-analysis/

3. Википедия

Другие ответы полезны, но в них отсутствуют свойства каждого из них:

График

^{Ненаправленный граф, источник изображения: Википедия}

^{Направленный граф, источник изображения: Википедия}

• Состоит из набора вершин (или узлов) и набора ребер, соединяющих некоторые или все из них.
• Любое ребро может соединить любые две вершины, которые еще не соединены одним и тем же ребром (в том же направлении, в случае ориентированного графа)
• Не обязательно должен быть связан (ребра не обязательно должны соединять все вершины вместе): один граф может состоять из нескольких несвязных наборов вершин.
• # P6 #

  # P7 #

Дерево

^{Источник изображения: Википедия}

• Тип графика
• Вершины чаще называют «узлами».
• Ребра направлены и представляют собой отношения "является дочерним элементом" (или "является родительским элементом").
• Каждый узел (кроме корневого) имеет ровно одного родителя (и ноль или более дочерних узлов)
• Имеет ровно один "корневой" узел (если в дереве есть хотя бы один узел), который является узлом без родителя.
• Должен быть подключен
• Является ацикличным, то есть не имеет циклов: «цикл - это путь [AKA sequence ] ребер и вершин, в которых вершина достижима из себя "

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

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

В графе может быть более одного пути, т.е. граф может иметь однонаправленные или двунаправленные пути (ребра) между узлами.

Также вы можете увидеть более подробную информацию: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

Деревья очевидны: это рекурсивные структуры данных, состоящие из узлов с дочерними элементами.

Карта (она же словарь) - это пары ключ / значение. Дайте карте ключ, и она вернет связанное значение.

Карты могут быть реализованы с использованием деревьев, надеюсь, вас это не смущает.

ОБНОВЛЕНИЕ: сбивающий с толку «график» для «карты» очень сбивает с толку.

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

Графы могут иметь однонаправленные или двунаправленные пути между узлами, быть циклическими или ациклическими и т. Д. Я бы посчитал графы более сложными.

Я думаю, что беглый поиск в любом приличном тексте структур данных (например, в «Руководстве по разработке алгоритмов») даст больше и более качественной информации, чем любое количество ответов SO. Я бы порекомендовал вам не идти по пассивному пути и начать самостоятельное исследование.

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

В графе каждый узел имеет один или несколько узлов-предшественников и узлов-преемников. График просматривается с использованием алгоритмов поиска в глубину (DFS) и поиска в ширину (BFS). График имеет цикл, поэтому он сложнее дерева. График - это сетевая модель. Есть два вида графов: ориентированные графы и неориентированные графы.

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

Дерево - это такой орграф, что:

а) со снятыми краевыми направлениями он связан и ацикличен

1. Вы можете удалить либо предположение, что он ацикличен.
2. Если это конечно, вы можете в качестве альтернативы удалить предположение, что это связано

б) каждая вершина, кроме одной, корня, имеет степень 1

в) корень имеет степень 0

1. Если существует только конечное число узлов, вы можете удалить либо предположение, что корень имеет степень 0, либо предположение, что узлы, отличные от корня, имеют степень 1.

Ссылка: http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf

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

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

Простая концепция: Дерево не имеет цикла и его однонаправленность, тогда как График формирует цикл, и он будет двунаправленным в некоторых случаях и однонаправленным в другом.