树和图这两种数据结构有什么区别？

Question

树和图这两种数据结构有什么区别？

searchdata-structuresdictionarytree

190

从学术角度来看，树形数据结构和图形数据结构的本质区别是什么？树形搜索和基于图形的搜索呢？

- user918304

12个回答

116

与其解释，我更喜欢用图片展示。

实时树形图

实时树形图

真实世界中的图形应用

实时图形

是的，地图可以被视为图形数据结构。

这样看起来会更容易。在我们知道每个节点只有一个父节点的地方使用树形图。但是图形可以具有多个前任（术语“父母”通常不用于图形）。

在现实世界中，您几乎可以使用图形来表示任何东西。例如，我使用了地图。如果将每个城市视为节点，则可以从多个点到达它。导致该节点的点称为前任，而该节点将引导到的点称为后继者。

电路图，房屋平面图，计算机网络或河流系统等技术图表也是图形的几个例子。许多现实世界的例子都可以视为图形。

技术图表可能如下所示：

树形图：

输入图像说明

图形：

输入图像说明

请确保参考以下链接。这些将回答您关于树和图的几乎所有问题。

参考：

- Sandeep

24

其他答案都很有用，但是它们缺少每个属性的解释：

图表

^{无向图，图片来源：维基百科}

^{有向图, 图片来源:维基百科}

由一组顶点（或节点）和连接它们的一组边组成
任何边都可以连接尚未通过相同边（在有向图中为同方向）连接的任意两个顶点
不必连接（边不必将所有顶点连接在一起）：单个图可以由几个不连通的顶点集组成
可以是有向或无向（适用于图中的所有边）
根据维基百科:

例如，如果顶点代表聚会上的人，并且如果两个人握手，则它们之间存在边缘，那么此图是无向的，因为任何人A只能与另一个人B握手，前提是B也与A握手。相反，如果从人A到人B的任何边缘对应于A欣赏B，则此图是有向的，因为欣赏不一定被回报。

树

^{图片来源：维基百科}

一种图表类型
节点更常被称为“节点”
边是有向的，代表一个“是子节点”（或“是父节点”）的关系
每个节点（除了根节点）都有一个父节点（和零个或多个子节点）
有且仅有一个“根”节点（如果树至少有一个节点），这是一个没有父节点的节点
必须连接
无环，意味着它没有循环：“循环是一条从一个顶点到自身的路径[也称为序列]”

上述属性存在一些重叠。具体来说，最后两个属性由其他属性暗示。但是所有这些属性仍然值得注意。

- Bernhard Barker

图片让理解变得如此简单！ - Raghav Gupta

“必须连接”这个说法是否多余，因为“每个节点（除了根节点）都恰好有一个父节点”？ - JamesTheAwesomeDude

@JamesTheAwesomeDude 是的，最后两个属性（连通和无环）由其他属性暗示或冗余。但我记录了所有这些属性，因为连通和无环是图论中重要的术语，而其他属性则是树的通常思考方式的表述。 - Bernhard Barker

11

TREE :
 1. Only one path exist between two vertices (Nodes).
 2. Root node is the starting node of the tree.
 3. Tree doesn't have loops.
 4. Number of edges: n-1 (where n is number of nodes)
 5. Tree looks like Hierarchical
 6. All trees are graph.

GRAPH :
 1. More than one path is allowed between two vertices.
 2. There is no root node concept (we can start from any node).
 3. There can be loop in graph.
 4. Number of edges are not defined.
 5. Graph looks like Network.
 6. All graphs are not tree.

你可以在这个视频中找到更详细的解释 -> https://www.youtube.com/watch?v=KVHrjVTp9_w

- spirito_libero

6

树是一种特殊的图形结构，即最小连接图，并且在任意两个顶点之间只有一条路径。

而在图形结构中，可能存在多条路径，即节点之间可以有单向或双向路径（边）。

您还可以查看更多细节：http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

- Bipon Biswas

2

简单来说，树不会形成循环，是单向的，而图可以形成循环，在某些情况下是双向的，在另一些情况下是单向的。

- Velkumaran A P

2

树（Tree）基本上是一种无向图，不包含环路，因此我们可以说树是图的一种更为限制的形式。然而，在编程中，树和图有不同的应用来实现各种算法。例如，图可以用于建模道路地图，而树可以用于实现任何分层数据结构。

- patel dhruv

1

一棵树是一个有向图，满足以下条件： a）在去除边方向后，它是连通且无环的

可以去掉它无环的假设
如果它是有限的，你也可以去掉它连通的假设

b）每个顶点（除了根）的入度为1 c）根的入度为0

如果节点只有有限多个，你可以去掉根的入度为0或者除根以外的节点度数为1的假设

参考资料：http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf

- BPL

0

在树中，每个节点（除了根节点）都有一个前驱节点和一个或两个后继节点。可以使用中序遍历、先序遍历、后序遍历和广度优先遍历来遍历它。树是一种特殊的图形，没有循环，因此被称为DAG（有向无环图）。树是一种分层模型。

在图中，每个节点都有一个或多个前驱节点和后继节点。通过使用深度优先搜索（DFS）和广度优先搜索（BFS）算法来遍历图形。图形具有循环，因此比树更复杂。图形是一种网络模型。有两种类型的图形：有向图和无向图。

- user10514540

3

树节点可以有零个或多个后继节点，而不仅仅是一个或两个。二叉树将后继/子节点的数量限制为2，但每棵树都有没有子节点的叶节点。 - Aaron

0

树中只有一个根节点，每个子节点最多只有一个父节点。然而，图没有根节点的概念。另一个区别是，树是层次模型，而图是网络模型。

- Rajan Kumar Kharel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user785287 · Accepted Answer

树（Tree）只是图（Graph）的一种特殊形式。

树具有方向性（父节点/子节点关系），且不包含环路，属于有向无环图（Directed Acyclic Graphs，DAG）的一种。因此，树是一种带有限制条件的 DAG，其限制条件为一个子节点只能有一个父节点。

需要指出的一件事是，树不是递归数据结构。由于上述限制条件，它们不能被实现为递归数据结构。但是，任何 DAG 实现（通常不是递归的）都可以使用。我偏好的树的实现方式是集中式 map 表示，并且是非递归的。

通常对图进行广度优先搜索或深度优先搜索，树也同样适用。