algorithm -使用图和树可以解决或更容易解决哪些问题?

Translate

这两种数据结构可以解决的最常见问题是什么?

在书上提出以下建议对我也很好:

  • 实施结构
  • 实现并解释使用它们的算法的推理
This question and all comments follow the "Attribution Required."

所有的回答

Translate

当我阅读此问题时,我想到的第一件事是:哪些类型的事物使用图/树?然后我回想起如何使用它们。

例如,采用树的两种常见用法:

  • DOM
  • 文件系统

DOM和XML类似于树结构。
alt text

这也是有道理的。这是有道理的,因为需要如何安排这些数据。文件系统也是如此。在UNIX系统上,有一个根节点,并在下面分支。挂载新设备时,就是将其连接到树上。

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

至于容易,我认为那是相对的。您是否擅长使用遍历树/图的递归函数?如果您需要平衡树怎么办?

考虑一个解决单词搜索难题的程序。您可以将单词搜索的所有字母映射到一个图形中,然后检查周围的节点以查看该字符串是否与任何单词匹配。但是,难道您不可以对单个阵列做同样的事情吗?您真正需要做的就是移动索引以左右检查字母,并按宽度检查上方和下方的字母。用图形解决这个问题并不难,但是如果您不习惯使用它们,它会带来很多额外的工作和难度-当然,这不应该使您灰心,尤其是当您正在学习他们。

我希望这可以帮助您考虑这些结构。至于推荐书,我不得不算法导论.

来源
Translate

电路图。

编译(有向无环图)

地图。非常紧凑的图形。

网络流量问题。

决断树木用于专家系统(原文如此)

鱼骨图,用于故障查找,过程改进,安全性分析。为了获得加分,请将您的错误恢复代码实现为鱼骨图。

来源
Translate

几乎所有问题都可以根据图论进行重写。我不是在开玩笑,请看任何有关NP完全问题的书,因为我们有很好的工具来处理图,所以有些古怪的问题变成了图论...

来源
Translate

算法设计手册包含一些有趣的案例研究,创造性地使用了图表。尽管它的名字,这本书还是很可读,甚至有时很有趣。

来源
Translate

我的大学有一门关于此类事情的课程:CSE 326。我认为这本书没有太大用处,但是这些项目很有趣,并且可以教您一些有关实现一些简单结构的知识。

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

来源
King Lee
Translate

Java算法:第5部分Robert Sedgewick撰写的所有内容都涉及图算法和数据结构。如果您想实现一些图形算法,这将是一本很好的第一本书。

来源
Translate

用于在游戏和多媒体应用程序中绘制图形的场景图大量使用树和图。节点代表要渲染的对象,转换,控件,组...

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

来源
Translate

@DavidJoiner /全部:

FWIW:的新版本算法设计手册现在应该在任何一天到期。

他的斯基埃纳教授为这本书开发的整个课程也可以在网上找到:

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

来源
Translate

由于树具有递归特性,因此在函数式编程语言中更多地使用了树。

同样,图形和树是建模许多AI问题的好方法。

来源
Translate

游戏通常使用图形来促进在整个游戏世界中寻找路径。世界的图形表示可以使用诸如广度优先搜索或A *之类的算法,以查找穿过它的路线。

他们还经常使用树来表示世界内的实体。如果您有成千上万个实体,并且需要在某个位置找到一个实体,则对列表进行线性迭代可能会效率低下,尤其是在您需要经常进行迭代时。因此,可以将该区域细分为一棵树,以便更快地对其进行搜索。正如可以通过二分搜索有效地搜索线性空间(从而将其划分为二叉树)一样,可以将2D空间划分为四叉树和3D空间八叉树.

来源