问为什么DFS在尝试查找Boggle板中的所有有效单词时都能工作

EN

您可以应用DFS或其他图形算法，因为您基本上也可以在带有对角线的grid graph上进行游戏。

​

​

把你的字母而不是点，你就有了你的图表。那么为什么DFS会在这里工作呢？

当你在这个游戏中创建一个单词时，你连接了相邻的顶点，从而在图形上创建了一条路径。因此，这里有一种方法，您可以开始使用(并改进)。

1. 创建一组所有英文字母的单词和一个合理长度的单词(让我们假设单词长度不超过N个字符)
2. 从顶点开始迭代，并从每个顶点调用DFS，直到长度为N。对于每个单词(规则中大于3的单词)，检查它是否在字典中，以及是否存在--将它们保存在某个地方。

您可以看到，在我的图表部分，您可以很容易地找到单词TORUS。

为什么使用DFS而不是BFS是有意义的？有几个原因：

• easier to implement
• way smaller space complexity

更容易实现更小的空间复杂性

我的算法的复杂度是多少，假设你有一个网格n * m，最长的单词有一个长度d。因为在我的算法中，你从所有顶点实现DFS，DFS的复杂度是O(b^d)，其中平均分支略小于8(可能甚至小于7，因为这里不能有循环)。在集合id O(1)中的搜索。所以复杂性是m * n * 8^d。

你如何改进它？尝试搜索单词TLRSOU没有什么意义，因为在英语字母表中没有以TLR开头的单词。因此，一个更好的想法是将单词存储在trie中，并快速终止没有意义的分支。

这是因为它是(或者可以)用图表示的。错别字是由水平、垂直或对角排列的相邻字母组成的。所以你可以按照这个规则画出字母之间的连接图。此外，DFS不会访问一个节点两次，因为它保存了一个已经访问过的节点列表。因此，它满足另一个规则，即一个字母只能使用一次。

DFS (和BFS也是如此)最终将发现图形中的每条路径，因此您可以将生成的路径列表与有效单词字典进行比较，以确定来自单个Boggle board的有效单词总数。

DFS最广为人知的用途当然是用于寻路-几乎任何空间都可以映射到图中，然后找到最短或最长的路径。DFS可以很好地找到图的半径，从而找到最中心的节点。这对于像整体填充算法这样的东西很有用，在这种算法中，您希望快速填充不规则形状的内部，因为从图形中心开始时，边扩展将发生得最快。