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

Question

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

对我来说,对以下书籍提出建议也是好事:

• 实施结构
• 实现并解释使用它们的算法的推理

Answer 1

当我读到这个问题时,我想到的第一件事是:什么类型的东西使用图形/树木？然后我回想起如何使用它们.

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

• DOM
• 文件系统

DOM和XML就像树结构一样.

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

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

至于更容易,我认为这是相对的.您是否适合使用递归函数遍历树/图？如果你需要平衡树怎么办？

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

我希望这能帮助你思考这些结构.至于书籍推荐,我必须选择算法导论.