树和图之间的区别
作者:
Laura McKinney
创建日期:
3 四月 2021
更新日期:
19 十月 2024
内容
树和图属于非线性数据结构的类别,其中树提供了一种非常有用的方式来表示层次结构中的节点之间的关系,并且图遵循网络模型。树和图的区别在于,树结构必须连接并且永远不会有循环,而图中没有这种限制。
非线性数据结构由分布在平面上的元素的集合组成,这意味着元素之间不存在线性数据结构中的这种顺序。
-
- 比较表
- 定义
- 关键差异
- 结论
比较表
比较依据 | 树 | 图形 |
---|---|---|
路径 | 两个顶点之间只有一个。 | 允许使用多个路径。 |
根节点 | 它只有一个根节点。 | 图没有根节点。 |
循环 | 不允许循环。 | 图可以有循环。 |
复杂 | 不太复杂 | 比较复杂 |
遍历技术 | 预购,订购和后购。 | 广度优先搜索和深度优先搜索。 |
边数 | n-1(其中n是节点数) | 没有定义的 |
型号类型 | 分层的 | 网络 |
树的定义
一种 树 是通常称为节点的数据项的有限集合。如上所述,树是一种非线性数据结构,它按排序顺序排列数据项。它用于显示各种数据元素之间的层次结构,并将数据组织到与信息相关的分支中。在树中添加新边缘会形成环路或电路。
有几种类型的树,例如二叉树,二叉搜索树,AVL树,线程二叉树,B树等。数据压缩,文件存储,算术表达式的操纵和游戏树是其中的一些应用数据结构。
树的属性:
- 在树的顶部有一个指定的节点,称为树的根。
- 剩余的数据项分为不相交的子集,称为子树。
- 树的高度向底部扩展。
- 必须连接一棵树,这意味着必须存在从一个根到所有其他节点的路径。
- 它不包含任何循环。
- 一棵树有n-1条边。
与树相关联的术语有很多,例如终端节点,边缘,级别,程度,深度,森林等。在这些术语中,下面描述其中一些。
- 边缘 –连接两个节点的线。
- 水平 –将树划分为多个级别,以使根节点位于级别0。然后,其直接子级位于级别1,其直接子级位于级别2,依此类推,直至终端节点或叶节点。
- 学位 –它是给定树中节点的子树数。
- 深度 –它是给定树中任何节点的最大级别,也称为 高度.
- 终端节点 –最高级别的节点是终端节点,而除终端节点和根节点之外的其他节点称为非终端节点。
图的定义
一种 图形 也是一种数学非线性数据结构,可以表示各种物理结构。它由一组顶点(或节点)和连接这两个顶点的一组边组成。图上的顶点表示为点或圆,而边缘表示为圆弧或线段。边由E(v,w)表示,其中v和w是成对的顶点。从电路或连接图中删除边会创建一个树形子图。
这些图被分为各种类别,例如有向图,无向图,连接图,非连接图,简单图和多图。计算机网络,交通系统,社交网络图,电路和项目计划是图数据结构的一些应用。它也用于名为 珀特 (计划评估和审核技术)和 每千次展示费用 (关键路径法),其中分析了图的结构。
图的属性:
- 可以使用边将图中的一个顶点连接到任意数量的其他顶点。
- 边缘可以是双向的或定向的。
- 边缘可以加权。
在图中,我们还使用了各种术语,例如相邻的顶点,路径,循环,度,连接图,完整图,加权图等。让我们了解其中的一些术语。
- 相邻顶点 –如果存在边(a,b)或(b,a),则顶点a与顶点b相邻。
- 路径 –来自随机顶点w的路径是相邻的顶点序列。
- 周期 –这是第一个和最后一个顶点相同的路径。
- 学位 –它是入射在顶点上的许多边。
- 连接图 –如果存在从随机顶点到任何其他顶点的路径,则该图称为连通图。
- 在树中,任何两个顶点之间仅存在一条路径,而图在节点之间可以具有单向和双向路径。
- 在树中,只有一个根节点,每个子节点只能有一个父节点。相反,在图中,没有根节点的概念。
- 一棵树不能有循环和自循环,而图可以有循环和自循环。
- 图更复杂,因为它可以具有循环和自循环。相反,与图形相比,树很简单。
- 使用预排序,有序排序和后排序技术遍历树。另一方面,对于图遍历,我们使用BFS(宽度优先搜索)和DFS(深度优先搜索)。
- 一棵树可以有n-1个边。相反,在图中,没有预定义的边数,它取决于图。
- 树具有层次结构,而图具有网络模型。
结论
图和树是用于解决各种复杂问题的非线性数据结构。图是一组顶点和边,其中一条边连接一对顶点,而一棵树被认为是最小连接图,必须连接并且没有环。