java - 使用 BFS 时，为什么我的 Words 没有在无向/未加权图中连接？

Question

问题在我的代码中，不知道为什么在用单词构建的图表中找不到任何连接。

ArrayList<String> words = new ArrayList<String>();
words.add("hello");
words.add("there");
words.add("here");
words.add("about");
                
Graph g = new Graph(words.size());
for(String word: words) {
  for(String word2: words){
       g.addEdge(words.indexOf(word), words.indexOf(word2));
  }
}

BufferedReader readValues = 
    new BufferedReader(new InputStreamReader(new FileInputStream("values.txt")));

while(true)
{
    String line = readTestFile.readLine();
    if (line == null) { break; }
    assert line.length() == 11; 
    String start = line.substring(0, 5);
    String goal = line.substring(6, 11);
            
    BreadthFirstPaths bfs = new BreadthFirstPaths(g, words.indexOf(start));
    if (bfs.hasPathTo(words.indexOf(goal))) {
    System.out.println(bfs.distTo(words.indexOf(goal)));
     for (int v : bfs.pathTo(words.indexOf(goal))) {
               System.out.println(v);
     }
    }
    else System.out.println("Nothing");
}

文本文件的内容:

hello there
hello here
about here

我好像得到:

Nothing
Nothing
Nothing
Nothing
Nothing 

不知道为什么？
编辑:OP 似乎在这里的代码有问题，尤其是图表。我不知 Prop 体是为什么，但是，我相信有人这样做。

Answer 1

我想您正在使用 Robert Sedgewick 和 Kevin Wayne 关于 Java 算法实现的优秀著作中的源代码 Algorithms, 4th Edition .
您的代码没有理由不能正常工作。请根据您的代码考虑以下测试:

public static void main(String... args) throws IOException {
  ArrayList<String> words = new ArrayList<String>();
  words.add("hello");
  words.add("there");
  words.add("here");
  words.add("about");

  Graph g = new Graph(words.size());
  for(String word: words) {
    for(String word2: words){
      g.addEdge(words.indexOf(word), words.indexOf(word2));
    }
  }

  BufferedReader readValues = null;

  try {

    readValues =
        new BufferedReader(new InputStreamReader(new FileInputStream("values.txt")));

    String line = null;
    while ((line = readValues.readLine()) != null) {
      // assert line.length() == 11;
      String[] tokens = line.split(" ");
      String start = tokens[0];
      String goal = tokens[1];

      BreadthFirstPaths bfs = new BreadthFirstPaths(g, words.indexOf(start));
      if (bfs.hasPathTo(words.indexOf(goal))) {
        System.out.println("Shortest path distance from " + start + " to " + goal + " = " + bfs.distTo(words.indexOf(goal)));
        StringBuilder path = new StringBuilder();
        String sep = "";
        for (int v : bfs.pathTo(words.indexOf(goal))) {
          path.append(sep).append(v);
          sep = " -> ";
        }

        System.out.println("Shortest path = " + path.toString());
      } else System.out.println("Nothing");
    }

  } finally {
    if (readValues != null) {
      try {
        readValues.close();
      } catch (Throwable t) {
        t.printStackTrace();
      }
    }
  }
}

如果您使用您指定的文本文件运行此程序，它将产生类似于以下内容的输出:

Shortest path distance from hello to there = 1
Shortest path = 0 -> 1
Shortest path distance from hello to here = 1
Shortest path = 0 -> 2
Shortest path distance from about to here = 1
Shortest path = 3 -> 2

我介绍的主要变化是与 start的计算相关的代码。和 goal变量:

String[] tokens = line.split(" ");
String start = tokens[0];
String goal = tokens[1];

我假设您正在使用另一个文本文件，也许是另一个代码；如果提供断言将失败或 StringIndexOutOfBounds计算 goal 时会引发异常如 substring来自索引 6至 11 .
除此之外，该算法应该可以正常工作。
话虽如此，请注意，您正在构建一个超连通图，其中每个节点都有一条直接通往不同节点及其自身的路径。也许这可能是您的目标，但请注意，当您做其他类型的事情时，事情会变得有趣。
例如，如果不是这个代码:

for(String word: words) {
  for(String word2: words){
    g.addEdge(words.indexOf(word), words.indexOf(word2));
  }
}

你尝试这样的事情:

g.addEdge(words.indexOf("hello"), words.indexOf("there"));
g.addEdge(words.indexOf("hello"), words.indexOf("about"));
g.addEdge(words.indexOf("about"), words.indexOf("here"));

算法的输出更有意义:

Shortest path distance from hello to there = 1
Shortest path = 0 -> 1
Shortest path distance from hello to here = 2
Shortest path = 0 -> 3 -> 2
Shortest path distance from about to here = 1
Shortest path = 3 -> 2