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

Question

С академической точки зрения, в чем принципиальная разница между структурой данных Tree и Graph?А как насчет поиска по дереву и по графику?

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

Дерево:

График:

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

Ссылки:

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. Википедия

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

График

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

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

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

• Может быть направленным или ненаправленным (что будет применяться ко всем ребрам в графе)
  Согласно Wikipedia :

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

Дерево

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

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

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

Answer 6

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

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

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

ОБНОВЛЕНИЕ: Запутывание "графика" для "карты" очень запутанно.

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

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

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

Answer 7

Дерево является орграфом таким, что:

a) с удаленными направлениями ребер, оно связано и ациклично

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

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

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

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

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

Answer 8

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

Answer 9

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