使用图和树可以解决或更容易地解决哪些问题?[关闭]

当我读到这个问题时,我首先想到的是: 什么类型的事物使用图表/树? 然后我回想我如何使用它们。

例如,以树的两个常见用途为例:

• DOM
• 文件系统

DOM和XML就类似于树结构。

这也是有道理的。 这是有意义的,因为需要如何安排这些数据 . 还有一个文件系统。在一个Unix系统上有一个根节点,并在下面进行分支。当你安装一个新设备时,你将它连接到树上。

您还应该问自己:数据是否属于这种类型的结构?创建对问题有意义的数据结构,其余的将遵循。

就简单点而言,我认为这是相对的。您是否擅长使用递归函数遍历树/图?如果你需要平衡这棵树怎么办?

想想一个解决单词搜索难题的程序。您可以将单词搜索的所有字母映射到一个图表中,并检查周围的节点,以查看该字符串是否匹配任何单词。但你不能只对一个数组做同样的操作吗?你真正需要做的就是移动一个索引来检查左右两边的字母,并根据宽度来检查上面和下面的字母。用图表来解决这个问题并不困难,但是如果你不习惯使用它们,它会带来很多额外的工作和困难——当然,这不会阻止你去做,尤其是当你正在学习它们的时候。

我希望这能帮助你思考这些结构。至于推荐书,我得同意 Introduction to Algorithms .

电路图。

编译(有向非循环图)

地图。非常紧凑的图形。

网络流问题。

决定 树 专家系统(SIC)

用于故障查找、过程改进、安全分析的鱼骨图。对于奖励点,将错误恢复代码作为 是 鱼骨图。

几乎每一个问题都可以用图论来重写。我不是在开玩笑,看看任何一本关于NP完全问题的书,有一些非常古怪的问题变成了图论,因为我们有很好的工具来处理图…

The Algorithm Design Manual 包含一些有趣的案例研究,并创造性地使用图形。尽管它的名字,这本书是非常可读的,甚至有时娱乐。

在我的大学里有一门这样的课程: CSE 326 . 我不认为这本书太有用,但是这些项目很有趣,并且教会了你一点关于实现一些简单结构的知识。

例如,树解决的一个最常见的问题(按使用它的人数)是手机文本输入。您可以使用树(不一定是二进制的)来表示可能出现的单词空间,这些单词可以从用户快速输入的任何给定数字列表中出来。

Algorithms for Java: Part 5 罗伯特·塞奇威克所著的《关于图形算法和数据结构》。如果你想实现一些图形算法,这将是一本很好的第一本书。

用于在游戏和多媒体应用程序中绘制图形的场景图大量使用树和图形。节点表示要呈现的对象、转换、控件、组…

场景图通常有多个层和属性,这意味着只能以指定的顺序(层)绘制图(属性)的某些节点。根据场景图的类型,它可以有两个parralel结构:声明和实例化。钍

@Davidjoiner/全部:

新版本的 Algorithm Design Manual 现在任何一天都到期。

斯基纳教授为这本书编写的整个课程也可以在网上找到:

http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html

由于树的递归性,它们在函数式编程语言中使用得更多。

此外,图和树是模拟许多人工智能问题的好方法。

游戏通常使用图表来帮助找到游戏世界中的路径。世界的图形表示可以使用诸如广度优先搜索或*之类的算法,以便找到穿过它的路径。

他们还经常使用树来表示世界上的实体。如果您有数千个实体,并且需要在某个位置找到一个实体,那么通过列表线性迭代可能效率很低,特别是如果您需要经常这样做。因此,该区域可以细分为一棵树,以便更快地进行搜索。正如线性空间可以通过二叉搜索(从而划分为二叉树)进行有效搜索一样,二维空间也可以划分为 quadtree 和三维空间 octree .