logo标签列表

使用图表和树形结构可以更轻松地解决哪些问题？

algorithmdata-structurestreecomputer-sciencegraph-theory
17

这两种数据结构最常见的问题是什么？

另外，对于以下方面的书籍推荐也会很有帮助：

  • 实现这些数据结构
  • 实现并解释使用它们的算法的原理
10个回答
17
当我阅读这个问题时，我首先想到的是：{{哪些事物使用图/树？}}然后我会回溯思考如何使用它们。
例如，以树的两个常见用途为例：
- DOM - 文件系统
DOM和XML类似于树形结构。
alt text 这也是有道理的。因为数据需要被安排，文件系统也是如此。在UNIX系统上，有一个根节点，在下面分支。当您挂载新设备时，将其附加到树上。
您还应该问自己：{{数据是否适合这种类型的结构？}}创建对问题和解决方案有意义的数据结构，其他内容将随之而来。
就易用性而言，我认为这是相对的。您是否熟悉用于遍历树/图的递归函数？如果需要平衡树怎么办？
想象一下解决单词搜索谜题的程序。您可以将所有单词搜索字母映射到图中，并检查周围的节点以查看该字符串是否与任何单词匹配。但是，您不能只使用单个数组做同样的事情吗？你真正需要做的就是移动索引以检查左右字母，通过宽度检查上下字母。使用图解决此问题并不困难，但如果您不习惯使用它们，则可能会创建很多额外的工作和困难-当然，这不应该阻止您这样做，特别是如果您正在学习它们。

我希望这能帮助你思考这些结构。至于书籍推荐，我会选择算法导论。

4

电路图。

编译（有向无环图）

地图。作为图形非常紧凑。

网络流问题。

专家系统的决策树（错别字）

故障排查、流程改进、安全分析的鱼骨图。为了加分，请将您的错误恢复代码实现为对象，这些对象就是鱼骨图。

3

几乎每个问题都可以用图论重新表达。我不是在开玩笑，看看任何一本关于NP完全问题的书，有一些非常疯狂的问题会被转化为图论，因为我们有很好的工具来处理图形...

2

算法设计手册包含了一些有趣的案例研究，其中创意运用了图形。尽管其名称为“算法设计手册”，但这本书非常易读，有时甚至很有趣。

1

游戏通常使用图形来方便地找到游戏世界中的路径。世界的图形表示可以使用广度优先搜索或A*等算法来查找其路径。

它们还经常使用树来表示世界中的实体。如果您有数千个实体并需要在特定位置找到其中一个，则通过列表进行线性迭代可能效率低下，特别是如果您需要经常这样做。因此，该区域可以被细分为一棵树，以允许更快地进行搜索。就像线性空间可以通过二分搜索（因此被划分为二叉树）进行高效搜索一样，2D空间可以被划分为四叉树，3D空间可以被划分为八叉树。

1

由于其递归性质，树在函数式编程语言中的使用更加广泛。

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

1

在我的大学里有一门课程专门讲这些东西：CSE 326。我认为这本书并不是太有用，但是项目很有趣，可以教你实现一些较简单的结构。

至于例子，使用树解决的最常见问题（按使用人数计算）之一是手机短信输入。您可以使用树（不一定是二叉树）来表示可能出现在用户快速输入的任何给定数字列表中的单词空间。

1

Java算法：第5部分由Robert Sedgewick编写，主要介绍图形算法和数据结构。如果您想实现一些图形算法，这将是一个很好的首选书籍。

1

在游戏和多媒体应用程序中，用于绘制图形的场景图通常会大量使用树和图形。节点代表要呈现的对象、变换、控件、组等。

场景图通常具有多个层和属性，这意味着您可以按指定顺序（层）绘制图形中的某些节点（属性）。根据场景图的类型，它可能具有两个并行结构：声明和实例化。

1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接