BFS 五字链

Question

我需要一些有关 BFS 字链的作业的帮助。词链基于五个字母的词，当词 x 的最后四个字母在词 y 中时，两个词相连。例如，climb 和 blimp 是相连的，因为climb 中的 l、i、m 和 b 在单词 blimp 中。

建议使用来自 Sedgewick 算法第 4 版的定向 BFS 或对其进行修改。代码可以在这里找到：https : //algs4.cs.princeton.edu/40graphs/并使用以下代码读取数据文件以列出单词：

BufferedReader r =
    new BufferedReader(new InputStreamReader(new FileInputStream(fnam)));
ArrayList<String> words = new ArrayList<String>();
while (true) {
    String word = r.readLine();
    if (word == null) { break; }
    assert word.length() == 5;  // inputcheck, if you run with assertions
    words.add(word);
}

以及从文件中读取测试用例的以下代码：

BufferedReader r = 
    new BufferedReader(new InputStreamReader(new FileInputStream(fnam)));
while (true) {
    String line = r.readLine();
    if (line == null) { break; }
    assert line.length() == 11; // inputcheck, if you run with assertions
    String start = line.substring(0, 5);
    String goal = line.substring(6, 11);
    // ... search path from start to goal here
}

数据文件中的字是：

their
moist
other
blimp
limps
about
there
pismo
abcde
bcdez
zcdea
bcdef
fzcde

使用测试用例文件时...

other there
other their
their other
blimp moist
limps limps
moist limps
abcde zcdea

...输出应该是每个单词对之间的边数，如果单词之间没有路径，则为 -1。

1
1
-1
3
0
-1
2

我是处理图表的新手，我不确定如何使用 Sedgewick 的 BFS 并修改它以读取测试用例文件。任何帮助表示赞赏。

Answer 1

让我们假设n是数据集中的单词数。

首先，我们需要根据给定的条件下建立一个邻接表为所有上面的字，即有之间的边缘x和y当且仅当最后四个字母x中存在y。构建这个邻接表是一个 O(n^2 * w) 操作，其中 w 是数据集中每个单词的平均大小。

其次，我们所要做的就是对测试数据进行传统的 BFS。

这是main函数：

    public static void main(String[] args) throws IOException {
        // get words from dataset
        List<String> words = readData();
        // get the word pairs to test
        List<List<String>> testData = getTestData();
        // form an adjacency list
        Map<String, List<String>> adj = getAdjacencyList(words);
        
        // for each test, do a traditional BFS
        for (List<String> test : testData) {
            System.out.println(bfs(adj, test));
        }
    }

这是根据给定条件构建邻接表的函数：

    public static Map<String, List<String>> getAdjacencyList(List<String> words) {
        Map<String, List<String>> adj = new HashMap<>();
        for (int i = 0; i < words.size(); ++i) {
            String word = words.get(i);
            adj.put(word, adj.getOrDefault(word, new ArrayList<>()));
            for (int j = 0; j < words.size(); ++j) {
                if (i == j) continue;
                int count = 0;
                String other = words.get(j);
                for (int k = 1; k < 5; ++k) {
                    count += other.indexOf(word.charAt(k)) != -1 ? 1 : 0;
                }
                // if the condition is satisfied, there exists an edge from `word` to `other`
                if (count >= 4)
                    adj.get(word).add(other);
            }
        }

        return adj;
    }

这是 BFS：

    public static int bfs(Map<String, List<String>> adj, List<String> test) {
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>(); // to keep track of the visited words, since the graph is not necessarily a DAG
        String start = test.get(0);
        String end = test.get(1);
        // if `start` and `end` words are equal
        if (start.equals(end))
            return 0;

        q.add(start);
        visited.add(start);
        int count = 0;
        while (!q.isEmpty()) {
            count++;
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                String word = q.poll();
                for (String val : adj.get(word)) {
                    if (val.equals(end))
                        return count; // return the number of edges
                    if (!visited.contains(val)) // only add the words which aren't visited yet.
                        q.add(val);
                }
            }
        }
        return -1; // if there isn't any edge
    }