java - 使用 BFS 搜索表示 Java 中的 Word Chain 问题的图形

Question

我需要使用广度优先搜索来解决词链问题。我有一个包含 5 个字母单词的文本文件，目标是使用这些单词并创建一个图表，该图表显示基于第一个单词和最后四个字母的单词之间的联系(如果可以在下一个单词中找到它们)。例如攀登 → 飞艇 → 跛行 → pismo → 潮湿。所以 climb 去 blimp 因为他们都有 l, i, m 和 b, 但是 blimp 不能回去爬因为climb 的最后四个字母不在 blimp 中。

我不太确定如何解决这个问题并显示图形表示，以便我可以在其上使用 BFS。

我曾尝试使用 Sedgewicks 算法第 4 版在 Eclipse 中使用 Java 实现图形，但是它非常模糊，因为这些示例中似乎缺少步骤。我是初学者，所以我很感激基本步骤或代码示例以及基于 sedgewicks 算法的解释如何解决这个问题，因为我试图自己解决它但没有成功。

我想要一个显示有向图的程序，其中包含单词和单词(顶点)之间的边，并且还能够对其进行 BFS。

Answer 1

首先，为了性能，你构建了一个 Map<String, List<String>>标准化的 4 个字母组合到包含这 4 个字母的单词列表。

例如climb有 4 个字母的 5 种不同组合，可以导致单词:limb , cimb , clmb , clib , 和 clim .由于字母顺序无关紧要，您可以通过对字母进行排序来规范化:bilm , bcim , bclm , bcil , 和 cilm .

每个词都是图表中的一个节点，五个规范化的 4 字母组合可用于其他词的边的入站“端口”。有了 map ，您可以非常快速地找到您可以从给定节点导航到的所有单词节点，方法是获取最后 4 个字母，对其进行归一化，然后在 map 中查找(当然不包括节点本身)。

例如用词climb , blimp , 和 limps ，你会得到如下 map :

bcil -> climb
bcim -> climb
bclm -> climb
bilm -> climb, blimp
bilp -> blimp
bimp -> blimp
blmp -> blimp
cilm -> climb
ilmp -> blimp, limps
ilms -> limps
ilps -> limps
imps -> limps
lmps -> limps

当然，列表中只有一个单词的任何映射条目都是一个指向自身的单词，因此它们是无关紧要的，可以删除。虽然没有特别的理由在代码中实际这样做，但对于人类消费而言，有用的映射条目是:

bilm -> climb, blimp
ilmp -> blimp, limps

您现在可以构建优势:

climb --[bilm]-> blimp
blimp --[ilmp]-> limps
limps --[imps]-> 

这里没有 BFS。
构建 map 是O(n)。
创建节点是O(n)。
创建边缘是 O(n*m)，其中 m是每个节点的平均边数。自 m对于较大的图可能接近一个常数，它可以被消除。
这意味着总的解决方案是 O(n)。