Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

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

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

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

Дерево:

График:

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

Ссылки:

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

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

• Википедия

Ответ 3

Разница между графиком и древовидной структурой данных

деревья

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

2. Дерево - это особый случай графа, в котором нет циклов, цепей и самоконтролей.

3. В дереве есть ровно один корневой узел, и у каждого ребенка есть только один родитель.

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

5. Деревья являются менее сложными, чем графы, так как не имеют циклов, не имеют петель и все еще связаны.

6. Обход дерева - это особый случай обхода графа. Дерево перебирается в предзаказе, в порядке и после заказа (все три в алгоритме DFS или BFS)

7. В деревьях существует множество правил/ограничений для установления связей между узлами через ребра.

8. Деревья входят в категорию DAG: Направленные ациклические графы - это своего рода ориентированный граф, который не имеет циклов.

9. Различными типами деревьев являются: Двоичное дерево, Двоичное дерево поиска, AVL-дерево, Кучи.

10.Деревянные приложения: сортировка и поиск, такие как Tree Traversal & Binary Search.

11. Дерево всегда имеет n-1 ребер.

12. Дерево - это иерархическая модель.

диаграммы

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

   2. График может иметь циклы, схемы, а также может иметь собственные циклы.

3. В графе нет такого понятия корневого узла.

4.В графике нет таких родительских дочерних отношений.

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

6. Граф проходит через DFS: поиск в глубину и в BFS: алгоритм поиска в ширину

7. В графах нет таких правил/ограничений для соединения узлов через ребра.

8. Граф может быть циклическим или ациклическим.

9.Heaps. Существует в основном два типа графов: ориентированные и неориентированные графы.

10. Графические приложения: раскраска карт в OR (PERT & CPM), алгоритмы, раскраска графика, планирование заданий и т.д.

11. В графе нет. ребер зависит от графа.

12. Граф - это модель сети.

Пример дерева:

График:

Ответ 4

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

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

Ответ 5

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

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

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

Ответ 6

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

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

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

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

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

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

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

Ответ 7

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

Ответ 8

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

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

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

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

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

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

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

Ответ 9

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

график

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

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

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

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

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

дерево

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

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

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

Ответ 10

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