使用图表和树可以解决或更容易解决哪些问题？[关闭]
https://stackoverflow.com/questions/2988
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
这两种数据结构可以解决哪些最常见的问题？
如果我还可以推荐以下书籍，那就太好了：
- 实施结构
- 实现并解释使用它们的算法的推理
解决方案
看到这个问题我首先想到的是： 哪些类型的事物使用图形/树？ 然后我回想如何使用它们。
例如，以树的两种常见用途为例：
- DOM
- 文件系统
DOM 和 XML 都类似于树结构。
这也是有道理的。 这是有道理的，因为这些数据需要如何排列. 。也是一个文件系统。在 UNIX 系统上有一个根节点，并在下面分支。当您安装新设备时，您是将其连接到树上。
你还应该问自己：数据属于这种类型的结构吗？创建对问题有意义的数据结构，其余的就会随之而来。
至于更容易，我认为这是相对的。您擅长使用递归函数来遍历树/图吗？如果你需要平衡树怎么办？
考虑一个解决单词搜索难题的程序。您可以将单词搜索的所有字母映射到图表中，并检查周围的节点以查看该字符串是否与任何单词匹配。但是你不能对单个数组做同样的事情吗？您真正需要做的就是移动索引以检查左侧和右侧的字母，并移动宽度以检查上方和下方的字母。用图表解决这个问题并不困难，但如果您不习惯使用它们，它可能会带来很多额外的工作和困难 - 当然，这不应该阻止您这样做，特别是如果您正在学习他们。
我希望这可以帮助您思考这些结构。至于书籍推荐，我必须选择 算法简介.
其他提示
电路图。
编译（有向无环图）
地图。非常紧凑的图表。
网络流量问题。
决定 树 用于专家系统（原文如此）
用于故障查找、流程改进、安全分析的鱼骨图。为了获得奖励积分，请将错误恢复代码实现为以下对象： 是 鱼骨图。
几乎每个问题都可以用图论来重写。我不是在开玩笑，看看任何关于 NP 完全问题的书，有一些非常古怪的问题被转化为图论，因为我们有很好的工具来处理图......
算法设计手册 包含一些有趣的案例研究以及图表的创造性使用。尽管它的名字如此，这本书却非常具有可读性，有时甚至很有趣。
我的大学有一门这样的课程： CSE 326. 。我不认为这本书太有用，但是这些项目很有趣，并且教你一些关于实现一些更简单的结构的知识。
例如，用树解决的最常见问题之一（根据使用它的人数）是手机文本输入问题。您可以使用树（不一定是二元树）来表示可能的单词空间，这些单词可以从用户快速输入的任何给定数字列表中出来。
Java 算法：第五部分 Robert Sedgewick 的著作全是关于图算法和数据结构的。如果你想实现一些图算法，这将是一本很好的第一本书。
在游戏和多媒体应用程序中绘制图形的场景图大量使用树和图。节点代表要渲染的对象、转换、控件、组……
场景图通常具有多个图层和属性，这意味着您只能按指定顺序（图层）绘制图形的某些节点（属性）。根据场景图的类型，它可以有两个并行结构：声明和实例化。钍
@DavidJoiner /全部：
前言：新版本的 算法设计手册 现在随时到期。
Skiena 教授为本书编写的整个课程也可在网上获取：
http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html
由于树的递归性质，树在函数式编程语言中被更多地使用。
此外，图和树是对许多人工智能问题进行建模的好方法。
