树搜索和图搜索之间的区别


树和图属于非线性数据结构的类别,其中树提供了一种非常有用的方式来表示层次结构中的节点之间的关系,并且图遵循网络模型。树和图的不同之处在于,必须连接树结构,并且永远不能有循环,而在图中没有这种限制。

非线性数据结构由分布在平面中的元素的集合组成,这意味着元素之间没有像线性数据结构中那样的顺序。

比较图

比较依据形象的
Path两个顶点之间只有一个。More than one path is allowed.
根节点它只有一个根节点。The chart does not have a root node.
循环不允许循环。The graph can have loops.
复杂不太复杂Comparatively more complex
穿越技术预购,订购和后购。Search in breadth and search in depth.
边数n-1(其中n是节点数)Not defined
型号类型分层的

树的定义

一 棵树 就是通常被称为节点的数据项的有限集合。如前所述,树是一种非线性数据结构,它以有序的顺序排列数据项。它用于显示各种数据元素之间的层次结构,并在与信息相关的分支中组织数据。在树上添加新边会形成循环。

有多种类型的树,例如二叉树,二叉搜索树,AVL树,二叉树,B树等。数据压缩,文件存储,算术表达式操纵和游戏树是其中的一些。树的应用。数据结构。

树属性:

  • 在树的顶部有一个指定的节点,称为树根。

  • 剩余的数据项分为不连贯的子集,称为子树。

  • 树的高度向底部扩展。

  • 必须连接一棵树,这意味着必须存在从一个根到所有其他节点的路径。

  • 它不包含循环。

  • 一棵树有n-1条边。

与树相关联的术语有很多,例如终端节点,边缘,级别,程度,深度,森林等。在这些术语中,下面将对其中一些进行描述。

  • 边缘 -连接两个节点的线。

  • 级别 :将树划分为多个级别,以使根节点位于级别0。然后,其直接子级位于级别1,其直接子级位于级别2,依此类推,直到终端或节点叶为止。

  • 程度 :是给定树中节点的子树数。

  • 深度 :是给定树中任何节点的最大级别,也称为 高度 。

  • 终端节点: 最高级别的节点是终端节点,而除终端节点和根节点之外的其他节点称为非终端节点。

图表定义

甲 图表 也是非线性数学数据结构可表示各种类型的物理结构。它由一组顶点(或节点)和一组连接这两个顶点的边组成。图形上的顶点表示为点或圆,而边缘显示为弧或线段。边由E(v,w)表示,其中v和w是成对的顶点。从连接的电路或图形中删除边会创建一个子图,该子图是一棵树。

图形分为几类,例如有向,无向,已连接,未连接,简单和多图形。计算机网络,运输系统,社交网络图,电路和项目计划是图数据结构的一些应用。它也用于 分析图结构的 称为 PERT  (程序评估和评估技术)和 CPM(关键路径方法)的管理 技术中。

图的属性:

  • 可以使用边将图中的一个顶点连接到任意数量的其他顶点。

  • 边可以是双向的也可以是有向的。

  • 边缘可以加权。

在图中,我们还使用各种术语,例如相邻顶点,路径,循环,度,连接图,完整图,加权图等。让我们了解其中的一些术语。

  • 相邻顶点 :如果存在边(a,b)或(b,a),则顶点a与顶点b相邻。

  • 路径 -来自随机顶点w的路径是相邻的顶点序列。

  • 循环 :这是第一个和最后一个顶点相等的路线。

  • 度 -它是顶点处的一系列入射边。

  • 连通图 -如果存在从随机顶点到任何其他顶点的路径,则该图称为连通图。

树和图之间的主要区别

  1. 在树中,两个顶点之间只有一条路径,而图在节点之间可以具有单向和双向路径。

  2. 在树中,只有一个根节点,每个子节点只能有一个父节点。与图中不同的是,没有根节点的概念。

  3. 一棵树不能有循环和自循环,而图可以有循环和自循环。

  4. 图形更加复杂,因为它可以具有循环和自动循环。相比之下,与图相比,树是简单的。

  5. 使用预排序,有序排序和后排序技术遍历树。另一方面,对于图表遍历,我们使用BFS(宽度搜索)和DFS(深度搜索)。

  6. 一棵树可以有n-1边。相反,在图形中,没有预定义的边数,它取决于图形。

  7. 树具有层次结构,而图具有网络模型。

结论

图和树是用于解决各种复杂问题的非线性数据结构。图是一组顶点和边,其中一条边连接一对顶点,而一棵树被认为是必须连接且没有环的最小连接图。

以上是 树搜索和图搜索之间的区别 的全部内容, 来源链接: utcz.com/z/362245.html

回到顶部