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

139

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

user918304
источник

Ответы:

150

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

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

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

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

user785287
источник
8
Графики очень полезны и могут быть использованы для моделирования огромного количества вещей. Множество других структур данных можно рассматривать как граф с ограничениями. Например, односвязный список является частным случаем группы обеспечения доступности баз данных.
JR Garcia
7
@ user785287 что вы подразумеваете под централизованным представлением карты ?
Компьютерщик
36
«Деревья не являются рекурсивной структурой данных» вводит в заблуждение и неправильно. Дерево может быть представлено с нерекурсивной структурой данных (например, массив ребер; полное дерево, например, лежащее в основе двоичной кучи, может быть очень компактно представлено в массиве; существуют другие сжатые представления и т. Д. И т. Д.), но, вероятно, самый популярный и полезный способ их представления - использование рекурсивной структуры на основе указателей. Представление не уникально для деревьев без корней, но это несущественно.
j_random_hacker
2
Не совсем. У дерева не обязательно есть направление. en.wikipedia.org/wiki/Tree_(graph_theory) показывает пример дерева без направления. Они часто используются в биологических контекстах.
Михал Пальчевски
2
@ harshpatel991 деревья не направлены в том смысле, что: «X и Y находятся в родительско-дочерних отношениях» не имеет направления. Тем не менее, индивидуальные отношения: «X - дитя Y», а «Y - дитя X» - это направленные отношения. Направление указывает только на это; направление движения. В деревьях идея направления действительно не нужна, если она не имеет смысла (что чаще всего бывает с деревьями). По крайней мере, так я это вижу.
Костас Муратидис
105

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

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

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

График в реальной жизни

График в реальном времени

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

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

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

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

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

Дерево:

введите описание изображения здесь

График:

введите описание изображения здесь

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

Ссылки :

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

тк ..
источник
7

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

график

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

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

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

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

дерево

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

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

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

Бернхард Баркер
источник
3

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

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

Фуад Букредин
источник
2

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

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

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

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

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

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

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

duffymo
источник
1
Извините, я имею в виду график, я набрал карту.
user918304
"Запутывающий" график "для" карты "очень запутанный". :)
cpz
1
Сказать «графики сложнее, чем деревья» - все равно, что сказать: «Вороны более специализированы, чем птицы». Разве мы не должны вместо этого сказать, что «Все деревья являются графами, но не все графы являются деревьями»?
dudewad
Мне все равно шесть лет спустя. Конечно, вы можете использовать свое время лучше здесь.
duffymo
2

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

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

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

Бипон Бисвас
источник
0

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

Нарендер Шарма
источник
0

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

Раджан Кумар Харель
источник
0

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

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

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

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

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

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

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

BPL
источник
0

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

Патель Дхрув
источник