数据结构 Tree 和 Graph 有什么不同？

小开

树是显而易见的: 它们是由子节点组成的递归数据结构。

Map (又名 dictionary)是键/值对。给一个 Map 一个键，它就会返回相关的值。

地图可以用树来实现，我希望你不会觉得这很困惑。

更新: 将“图表”与“地图”混淆是非常令人困惑的。

图比树更复杂。树意味着递归的父/子关系。遍历树的自然方法有: 深度优先、广度优先、层次顺序等。

图可以在节点之间有单向或双向的路径，可以是循环的，也可以是非循环的，等等。我认为图表更为复杂。

我认为在任何像样的数据结构文本(例如“算法设计手册”)中粗略搜索一下，会比任何 SO 答案提供更多更好的信息。我建议你不要采取被动的方式，开始为自己做一些研究。

小开

树只是图的一种受限形式。

树有方向(父/子关系) ，不包含循环。它们属于有向无环图(或 DAG)的范畴。因此，树是 DAGs，其限制是一个子节点只能有一个父节点。

需要指出的是，树不是递归的数据结构。由于上述限制，它们不能作为递归数据结构实现。但是任何 DAG 实现(通常不是递归的)也可以使用。我首选的 Tree 实现是一个集中的映射表示，并且是非递归的。

图通常先搜索宽度，后搜索深度，Tree 也是如此。

小开

在数学中，图表示一组对象，其中一些对象通过链接连接。相互连接的对象由称为顶点的数学抽象表示，连接一些顶点对的链接称为边。通常，一个图以图形的形式表示为顶点的一组点，边由直线或曲线连接。图形是离散数学的研究对象之一。

小开

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

小开

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

一棵实时的树

A tree in real time

图表在现实生活中的应用

A real time graph

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

看到他们这样，生活会轻松很多。在我们知道每个节点只有一个父节点的地方使用树。但是图可以有多个前辈(术语“父”通常不用于图)。

在现实世界中，您可以使用图表表示几乎任何东西。比如说，我用了一张地图。如果将每个城市视为一个节点，则可以从多个点到达。通向这个节点的点称为前辈，通向这个节点的点称为后继。

电路图、房屋平面图、计算机网络或河流系统都是图表的例子。许多真实世界的例子可以看作是图。

技术图可以是这样的

树木:

enter image description here

图片:

enter image description here

一定要参考下面的链接。这些链接几乎可以回答你所有关于树和图表的问题。

参考文献:

小开

树是图的一种特殊形式，即极小连通图，在任意两个顶点之间只有一条路。

在图中可以有多个路径，即图在节点之间可以有单向或双向的路径(边)

小开

树是一个有向图，这样:

A)去除边缘方向，它是连接和无环的

您可以删除任何一个假设，即它是无环的

如果它是有限的，您也可以移除它是连接的假设

B)除根点外的每个顶点都有1次方

C)根的度数为0

如果只有有限多个节点，则可以删除根为0的假设，或者删除根为0的假设根以外的节点具有度1

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

小开

在树中，每个节点(根节点除外)正好有一个前任节点和一个或两个后继节点。可以使用顺序遍历、预序遍历、后序遍历和宽度优先遍历。Tree 是一种特殊的图形，它没有循环，因此被称为 DAG (有向无环图)。树是一个分层的模型。

在图中，每个节点有一个或多个前置节点和后续节点。图表是使用深度优先搜索(dFS)和广度优先搜索优先搜索(bFS)算法来遍历的。图有圈，所以比树更复杂。图是一种网络模型。有两种图: 有向图和无向图。

小开

其他的答案是有用的，但是他们缺少了每个问题的属性:

图表

^{无向图图片来源: Wikipedia}

^{有向图，图片来源: Wikipedia}

由一组顶点(或节点)和一组连接部分或全部顶点的边组成
任何边都可以连接任意两个没有被相同边连接的顶点(在有向图的情况下，是在相同的方向上)
不必连接(边不必将所有顶点连接在一起) : 一个图可以由几个不连接的顶点集合组成
可以是有向的或无向的(这适用于图中的所有边)
根据维基百科:

例如，如果顶点代表聚会上的人，如果两个人握手，那么两人之间就有一条边，那么这个图是无向的，因为任何人 A 都可以与人 B 握手，只有当 B 也与 A 握手。相反，如果从一个人 A 到一个人 B 的任何边对应于 A 欣赏 B，那么这个图是有向的，因为欣赏不一定是相互的。

树

^{图片来源: Wikipedia}

一种图形
顶点通常被称为“节点”
边是有方向的，表示“是”(或“是父母”)关系的子女
每个节点(根节点除外)正好有一个父节点(和零个或多个子节点)
只有一个“根”节点(如果树至少有一个节点) ，这是一个没有父节点的节点
肯定有关联
是非循环的，意味着它没有周期: “一个循环是边和顶点的路径[ AKA 序列] ，其中一个顶点可以从它自己到达。”

上述属性有一些重叠之处。具体来说，其余的属性隐含了最后两个属性。尽管如此，所有这些都毫无价值。

小开

树基本上是不含圈的无向图，因此可以说树是图的更多限制形式。然而，在编程中，树和图在实现各种算法时有着不同的应用。例如，图可以用于模型路线图，树可以用于实现任何层次化的数据结构。

小开

简单的概念是 树不具有圈形式和单向性，而图形具有圈形式，在某些情况下是双向的，在另一些情况下是单向的。

小开

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