directed-acyclic-graphs - 有向无环图

Question

我无法理解第 9 页的有向无环图

http://mitpress.mit.edu/books/chapters/0262033844chap27.pdf

谁能解释一下？

Answer 1

如果这是您需要的一般理解，您可以这样想。它是“定向的”，因为它有一个方向。“非循环”，因为它是一种方式。然后，将图表视为一种在一个方向上导航的方式。

如果您将此视为应用于字典存储的示例，它可能非常有用。与其将字典中的每个单词都存储为平面文本文件，不如将它们存储为 DAG。这样做的好处是它占用更少的空间，并且可以非常快速地进行查找。

因此，您可以将诸如“hello”之类的单词存储为由不同字母组成的图形。每个字母都是一个“节点”。从“h”你会说好的，我从这里去哪里？该图将您引导至“e”，并从“e”引导至“l”，依此类推。

因此，“图”是一种导航方法，“有向”和“非循环”指的是如何完成导航。

希望这可以帮助。我对 DAG 的体验非常具体，因为我为字典实现了它。我希望这有助于您的理解。如果其他人有更好的理解，或者如果我歪曲了任何内容，请发表评论。