数据结构树和图之间有什么区别？

Question

从学术上讲,数据结构Tree和Graph之间的本质区别是什么？那么基于树的搜索和基于图的搜索呢？

Answer 1

树只是图形的限制形式.

树有方向(父/子关系),不包含周期.它们适用于有向无环图(或DAG)类别.所以树木是DAG,其限制是孩子只能拥有一个父母.

有一点值得指出,树不是递归数据结构.由于上述限制,它们不能实现为递归数据结构.但是也可以使用通常不是递归的任何DAG实现.我首选的Tree实现是一个集中的地图表示,并且不是递归的.

图形通常首先是搜索呼吸或首先是深度搜索.这同样适用于Tree.

Answer 2

而不是解释我更喜欢在图片中显示它.

一棵树实时

现实生活中使用的图表

是的,地图可以显示为图形数据结构.

像这样看待他们会让生活更轻松.树在我们知道每个节点只有一个父节点的地方使用.但是图形可以有多个前辈(术语父级通常不用于图形).

在现实世界中,您几乎可以使用图形表示任何内容.例如,我使用了地图.如果您将每个城市视为一个节点,则可以从多个点进行访问.导致此节点的点称为前置节点,此节点将导致的点称为后继节点.

电路图,房屋计划,计算机网络或河流系统是图表的更多例子.许多现实世界的例子可以被视为图表.

技术图可能是这样的

树:

图表:

请务必参考以下链接.这些将回答几乎所有关于树木和图表的问题.

参考文献:

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. 维基百科

Answer 3

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

图形

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

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

• 由一组顶点（或节点）和一组连接其中一些或全部的边组成
• 任何边都可以连接尚未通过相同边连接的任何两个顶点（在同一方向，在有向图的情况下）
• 不必连接（边不必将所有顶点连接在一起）：单个图可以由几个不连接的顶点集组成

• 可以是有向的或无向的（这将适用于图中的所有边）
  根据维基百科：

  例如，如果顶点代表参加聚会的人，并且如果他们握手，则两个人之间存在边，则此图是无向图，因为任何人 A 都可以与人 B 握手，前提是 B 也与 A 握手。相反，如果从人 A 到人 B 的任何边对应于 A 欣赏 B，则该图是有向的，因为欣赏不一定是互惠的。

树

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

• 一种图形
• 顶点通常被称为“节点”
• 边是有向的，表示“是其子代”（或“是其父代”）关系
• 每个节点（根节点除外）只有一个父节点（以及零个或多个子节点）
• 正好有一个“根”节点（如果树至少有一个节点），这是一个没有父节点的节点
• 必须连接
• 是非循环的，这意味着它没有循环：“循环是边和顶点的路径 [AKA 序列]，其中顶点可以从自身到达”

上述属性有一些重叠。具体来说，其余的属性隐含了最后两个属性。但所有这些都值得一提。

Answer 4

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

Answer 5

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

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

您还可以看到更多详细信息： http://freefeast.info/difference- Between/difference- Between-trees-and-graphs-trees-vs-graphs/

Answer 6

树很明显：它们是由带有子节点的节点组成的递归数据结构。

映射（又名字典）是键/值对。给映射一个键，它将返回关联的值。

地图可以使用树来实现，我希望您不会感到困惑。

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

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

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

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