directed-acyclic-graphs - 有向无环字图构造

Question

假设我的 DAWG 中有 3 个单词：do、dot、bot 我将拥有这个：

http://imageshack.us/photo/my-images/703/dawgp.png/

这张图告诉我们“bo”也是一个词。这确实不是。如果只有路径来自“d”而不是“b”，则节点“o”是 EOW

我显然很想念，但我现在知道是什么了。

Answer 1

好的，我想我更好地了解您要做什么以及 DAG 如何适合您的工作。如果您想要一个图表来表示包含单词“do”、“dot”和“bot”的字典，那么您将拥有边；

.->d->o'->t'
.->b->o->t'

在哪里 '。' 表示图的根，分支是完全独立的，即边“d->o”指向与“b->o”中提到的“o”不同的出现。通过试图让两条边都指向同一出现的“o”，你已经使图形格式不正确。

请注意，在我的“图表”中，我使用了一个 ' 符号来表示一个字母可以通过从词根读取到该符号来作为单词的结尾。如果以后有时间，我会更好地绘制图表。