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

这两种数据结构可以解决哪些最常见的问题?

对于我来说,对于书中的建议也是很好的:

  • 实施结构
  • 实施并解释使用它们的算法的推理
0
额外 编辑
意见: 1

9 答案

我在阅读这个问题时首先想到的是:什么类型的东西使用图/树?然后我回想我如何使用它们。

例如,采取树的两个常见用途:

  • DOM
  • 文件系统

The DOM, and xml for that matter, resemble tree structures.
alt text

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

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

只要更容易,我认为那是相对的。你用递归函数遍历一棵树/图是否合适?如果你需要平衡这棵树怎么办?

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

我希望这能帮助你思考这些结构。至于书籍推荐,我必须使用 算法简介 即可。

0
额外

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

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

0
额外

我的大学有这样的课程: CSE 326 。我并不认为这本书太有用,但是这些项目很有趣,并教你一些关于实现一些简单结构的一些事情。

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

0
额外

The Algorithm Design Manual contains some interesting case studies with creative use of graphs. Despite its name, the book is very readable and even entertaining at times.

0
额外

几乎所有的问题都可以用图论的方式来重新编写。我不是在开玩笑,看任何有关NP完整问题的书籍,还有一些非常古怪的问题转化为图论,因为我们有很好的工具来处理图表......

0
额外

由于其递归性质,树在函数式编程语言中被更多地使用。

另外,图形和树是模拟很多AI问题的好方法。

0
额外

游戏通常使用图表来帮助查找整个游戏世界的路径。世界的图形表示可以具有诸如广度优先搜索或A *的算法以便找到穿过它的路线。

他们还经常使用树来代表世界上的实体。如果您有成千上万的实体,并且需要在某个位置找到一个实体,那么通过列表线性迭代可能效率很低,尤其是在需要经常执行的情况下。因此,该区域可以细分为一棵树,以便更快地搜索它。就像线性空间可以用二进制搜索进行高效搜索一样(并因此被分成二叉树),二维空间可以分成一个四叉树和3D空间转换为八叉树

0
额外

电路图。

汇编(有向无环图)

地图。非常紧凑的图形。

网络流量问题。

为专家系统决策(原文如此)

用于故障查找,过程改进,安全分析的鱼骨图。对于奖励积分,请将您的错误恢复代码实施为 鱼骨图。

0
额外

@DavidJoiner / all:

FWIW:新版本的算法设计手册现在即将发布。

Skiena教授开发此书的整个过程也可以在网上找到:

http://www.cs.sunysb.edu/~ algorith /视频讲座/ 2007-1.html

0
额外