Граф и дерево в чем разница
График и дерево 2021
Граф против дерева
На графике есть три набора; это вершины, ребра и множество вместо связей между вершинами и ребрами. Схема представляет собой нерегулярную последовательность ребер и вершин, где по краям не повторяется. Вершины могут быть повторены, а начальная и конечная вершины идентичны. Дерево не может содержать какой-либо цикл и все еще может быть подключено. Кроме того, он называется скромно связанным графом, в котором существует только один путь, соединяющий две вершины.
Граф, подобный дереву, представляет собой набор узлов и ребер, но не содержит правил, определяющих корреляцию между узлами. Графики действительно являются одной из наиболее адаптируемых структур данных.
2. По сравнению с реальным деревом, его структура содержит узлы, которые связаны друг с другом. Каждый узел может иметь определенное значение или условие. Дерево также может стоять отдельно или может обозначать отдельную структуру данных.
3. Графики состоят из группы узлов и ребер, то же самое с деревьями, но в случае графиков правила для соединений между узлами не существуют.
4. На графике есть три набора; это вершины, ребра и множество вместо связей между вершинами и ребрами.
5. Дерево может не включать какой-либо цикл и все еще может быть подключено. Кроме того, он называется скромно связанным графом, где есть только один путь, соединяющий две вершины
В чем разница между деревом и графиком
Содержание:
главное отличие между деревом и графиком является то, что дерево организует данные в виде древовидной структуры в иерархии, в то время как граф организует данные в виде сети.
Ключевые области покрыты
1. Что такое дерево
— определение, функциональность
2. Что такое график
— определение, функциональность
3. В чем разница между деревом и графиком
— Сравнение основных различий
Основные условия
Двоичный поиск, график, линейные структуры данных, нелинейные структуры данных, дерево
Что такое дерево
Некоторые важные термины, связанные с деревом, заключаются в следующем. Вы можете увидеть эти функции и примеры в приведенном выше дереве.
корень узел самый верхний элемент данных в дереве. Элемент 8 является корневым узлом на изображении выше.
край помогает связать узлы. Например, в приведенном выше дереве ребра соединяются 8 и 3, 8 и 10.
родитель узел это узел, отличный от корневого узла, который соединяется с ребром вверх. Например, 3 является родительским узлом 1 и 6. Аналогично, 6 является родительским узлом 4 и 7.
ребенок узел это узел, который соединяется вниз по ребру. Например, 4 и 7 являются дочерними узлами 6.
Subtree является потомком узла. Например, раздел слева от корневого узла (8), который начинается с 3, является поддеревом. Точно так же раздел справа от корневого узла, который начинается с 10, является поддеревом.
уровень представляет поколение узлов. Например, корневой узел принадлежит уровню 0. 3, а 10 принадлежит уровню 1 и так далее.
Что такое график
Некоторые важные термины, связанные с графиком, заключаются в следующем.
Ребра ссылки, соединяющие вершины Например, ребра выше соединяют вершины A и B, вершины B и D и т. Д. Мы также можем записать ребра как E =
Дорожка представляет последовательность узлов, чтобы следовать для достижения узла назначения. Например, ABD представляет путь от вершины A до D.
Когда два узла соединяются друг с другом через ребро, они смежные узлы, Например, A и B являются смежными узлами. Аналогично, B и D являются смежными узлами.
В основном, есть два типа графов как ориентированные и неориентированные графы. Когда граф содержит упорядоченную пару вершин, это ориентированный граф, а когда граф содержит неупорядоченную пару вершин, это неориентированный граф.
Разница между деревом и графиком
Определение
Представление данных
Дерево представляет данные в форме древовидной структуры иерархически, в то время как график представляет данные, аналогичные сети. Следовательно, в этом главное отличие дерева от графа.
Корневой узел
Кроме того, еще одно важное отличие дерева от графа состоит в том, что в дереве есть корневой узел, а в графе нет корневых узлов.
Loops
Более того, наличие петель является еще одним отличием дерева от графа. В дереве нет циклов, а в графе могут быть циклы.
сложность
Кроме того, граф более сложен, чем дерево.
Заключение
В чем разница между структурой данных Tree и Graph?
С академической точки зрения, в чем принципиальное отличие структуры данных Tree и Graph? А как насчет поиска по дереву и по графику?
9 ответов
Деревья имеют направление (отношения родитель /потомок) и не содержат циклов. Они вписываются в категорию направленных ациклических графов (или DAG). Таким образом, деревья являются группами обеспечения доступности баз данных с ограничением на то, что у ребенка может быть только один родитель.
Вместо объяснения я предпочитаю показывать это в картинках.
Дерево в реальном времени
График в реальной жизни
Да, карту можно визуализировать как структуру данных графа.
Видя их такими, жизнь становится проще. Деревья используются в тех местах, где мы знаем, что у каждого узла есть только один родитель. Но у графиков может быть несколько предшественников (термин родитель обычно не используется для графиков).
В реальном мире вы можете представлять практически все, используя графики. Я использовал карту, например. Если вы рассматриваете каждый город как узел, до него можно добраться из нескольких точек. Точки, которые ведут к этому узлу, называются предшественниками, а точки, к которым ведет этот узел, называются преемниками.
Техническая схема может быть такой
Дерево:
График
Обязательно обратитесь к ссылкам ниже. Они ответят почти на все ваши вопросы о деревьях и графиках.
Разница между графиком и древовидной структурой данных
Деревья
В дереве ровно один корневой узел, и у каждого потомка есть только один родитель.
В деревьях есть родительские дочерние отношения, поэтому поток может быть там с направлением сверху вниз или наоборот.
5.Деревья менее сложны, чем графы, так как не имеют циклов, самоконтролей и все еще связаны.
7.В деревьях существует множество правил /ограничений для установления связей между узлами через ребра.
9. Различные типы деревьев: двоичное дерево, двоичное дерево поиска, дерево AVL, куча.
10.Деревянные приложения: сортировка и поиск, такие как Tree Traversal & Бинарный поиск.
11.Дерево всегда имеет n-1 ребер.
Графы
В графе может быть более одного пути, то есть граф может иметь однонаправленные или двунаправленные пути (ребра) между узлами
3.В графе нет такого понятия корневого узла.
4.В Graph нет таких родительских и дочерних отношений.
5. Графы являются более сложными по сравнению с деревьями, поскольку они могут иметь циклы, циклы и т. д.
6. Граф проходит через DFS: поиск в глубину и в BFS: алгоритм поиска в ширину
7.В графах нет таких правил /ограничений для соединения узлов через ребра.
8. Граф может быть циклическим или ациклическим.
9.Heaps. Существует в основном два типа графиков: ориентированные и неориентированные графы.
10.Графические приложения: раскраска карт в OR (PERT & CPM), алгоритмы, раскраска графика, планирование заданий и т. д.
Пример Дерево:
График:
В графе может быть несколько путей, т. е. граф может иметь однонаправленные или двунаправленные пути (ребра) между узлами
Деревья очевидны: это рекурсивные структуры данных, состоящие из узлов с дочерними элементами.
Карты могут быть реализованы с использованием деревьев, надеюсь, вас это не смущает.
ОБНОВЛЕНИЕ: Запутывание «графика» для «карты» очень запутанно.
Графики более сложные, чем деревья. Деревья подразумевают рекурсивные отношения между родителями и детьми. Существуют естественные способы обхода дерева: сначала глубина, ширина в ширину, порядок уровней и т. Д.
Графики могут иметь однонаправленные или двунаправленные пути между узлами, быть циклическими или ациклическими и т. д. Я бы посчитал графики более сложными.
Я думаю, что простой поиск по любому тексту приличных структур данных (например, «Руководство по разработке алгоритмов») дал бы больше и лучше информации, чем любое количество ответов SO. Я бы порекомендовал вам не идти по пассивному маршруту и начать проводить некоторые исследования для себя.
а) с удаленными направлениями ребер, он связан и ацикличен
б) каждая вершина, кроме одной, корня имеет степень 1
в) корень имеет степень 0
В чем разница между структурой данных Tree и Graph?
С академической точки зрения, в чем принципиальная разница между структурой данных Tree и Graph? А как насчет поиска по дереву и по графику?
Важно отметить, что деревья не являются рекурсивной структурой данных. Они не могут быть реализованы как рекурсивная структура данных из-за вышеуказанных ограничений. Но любая реализация DAG, которая обычно не является рекурсивной, также может быть использована. Моя предпочтительная реализация Tree представляет собой централизованное представление карты и не является рекурсивной.
Графики обычно ищутся по ширине или по глубине. То же самое относится и к дереву.
Вместо объяснения я предпочитаю показывать это в картинках.
Дерево в реальном времени
График в реальной жизни
Да, карта может быть визуализирована как структура данных графа.
Увидев их так, жизнь становится проще. Деревья используются в тех местах, где мы знаем, что у каждого узла есть только один родитель. Но графы могут иметь несколько предшественников (термин родитель обычно не используется для графов).
В реальном мире вы можете представлять практически все, используя графики. Я использовал карту, например. Если вы рассматриваете каждый город как узел, до него можно добраться из нескольких точек. Точки, которые ведут к этому узлу, называются предшественниками, а точки, к которым этот узел приведет, называются преемниками.
Техническая схема может быть такой
Дерево:
График:
Обязательно обратитесь по ссылкам ниже. Они ответят почти на все ваши вопросы о деревьях и графиках.
Другие ответы полезны, но им не хватает свойств каждого:
график
Может быть направленным или ненаправленным (что применимо ко всем ребрам в графе)
Согласно Википедии :
Например, если вершины представляют людей на вечеринке, и между двумя людьми есть грань, если они пожимают друг другу руки, тогда этот график является ненаправленным, потому что любой человек A может пожать руку человеку B, только если B также пожмет руку A. Напротив, если любое ребро от человека A человеку B соответствует A, восхищающемуся B, тогда этот граф направлен, потому что восхищение не обязательно отвечает взаимностью.
дерево
Существует некоторое совпадение в вышеуказанных свойствах. В частности, последние два свойства подразумеваются остальными свойствами. Но все же стоит отметить.
Деревья очевидны: это рекурсивные структуры данных, состоящие из узлов с дочерними элементами.
Карты могут быть реализованы с использованием деревьев, надеюсь, вас это не смущает.
ОБНОВЛЕНИЕ: Запутывание «графика» для «карты» очень запутанно.
Графики сложнее деревьев. Деревья подразумевают рекурсивные отношения родитель / ребенок. Существуют естественные способы обхода дерева: сначала глубина, ширина ширина, порядок уровней и т. Д.
Графы могут иметь однонаправленные или двунаправленные пути между узлами, быть циклическими или ациклическими и т. Д. Я считаю, что графы являются более сложными.
Я думаю, что простой поиск в любом тексте приличных структур данных (например, «Руководство по разработке алгоритмов») даст больше и лучше информации, чем любое количество ответов SO. Я бы порекомендовал вам не идти по пассивному маршруту и начать делать некоторые исследования для себя.
В чем разница между графом и деревом?
Какой граф является деревом?
Что такое лес графы?
Лесом называют граф, связные компоненты которого являются деревьями. В частности, дерево не может иметь петель и кратных ребер. Вершину графа, инцидентную только одному его ребру, называют концевой (или висячей) вершиной, а ребро, инцидентное концевой вершине, будем называть концевым ребром графа.
Чему равна степень листа дерева?
Степень дерева равна максимальной степени узла, входящего в дерево. Исходя из определения степени понятно, что степень узла бинарного дерева не превышает числа два. При этом листьями в дереве являются вершины, имеющие степень ноль.
Как проверить является ли граф деревом?
Неориентированный граф, состоящий из n вершин, будет деревом, если он связный и содержит n – 1 ребро. Запускаем поиск в глубину из первой вершины. Если существует обратное ребро, то граф имеет цикл и не является деревом.
Что называют деревом в информатике?
Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы.
Какой граф является связным?
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.
Какие графы являются изоморфными?
Два графа называются изоморфными, если у них одинаковое число вершин (обозначим его n) и вершины каждого из них можно занумеровать так числами от 1 до n, что в первом графе две вершины соединены ребром тогда и только тогда, когда вершины с такими же номерами во втором графе соединены. 1.
Какие графы ориентированные?
Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.
Какие бывают графы?
Ориентированные и неориентированные графы
Графы, в которых все рёбра являются звеньями (порядок двух концов ребра графа не существенен), называются неориентированными. Графы, в которых все рёбра являются дугами (порядок двух концов ребра графа существенен), называются ориентированными графами или орграфами.
Что определяет степень дерева?
Если элемент не имеет потомков, он называется листом или терминальным узлом дерева. Остальные элементы – внутренние узлы (узлы ветвления). Число потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева.
Что такое математическое дерево?
Как работает бинарное дерево?
Как определить является ли граф связным?
Если нужно просто проверить граф на связность, то считаем вершины, помеченные первым маркером, и сравниваем получившееся число с нулем. Если число вершин, помеченные первым маркером, равно нулю, то граф связный.
Какой граф называется взвешенным?
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра). См. Размеченный граф. Вполне несвязный граф (пустой граф, нуль-граф) — регулярный граф степени 0, то есть граф без рёбер.