为什么在使用 BFS 时我的单词没有在 Undirected/Unweighted 图表中连接？

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 似乎对这里的代码有问题，尤其是图表。我不知道具体为什么，但是，我肯定有人这样做。

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];

我假设您正在使用另一个文本文件，也许是另一个代码；对于提供的断言，当您计算 goal 作为从索引 6 到 11 的 substring 时，断言将失败或引发 StringIndexOutOfBounds 异常。

除此之外，该算法应该可以正常工作。

话虽这么说，请注意您正在构建一个图 超连接，其中每个节点都有通往不同节点及其自身的直接路径。也许那可能是你的 objective，但请注意，当你做其他事情时，事情会变得有趣。

例如，如果不是这个代码：

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

Answer 2

我想您使用的代码来自 Java Textbook

你的代码应该是

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;


public class words_sof {

    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));
            }
        }

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

            while (true) {
// ORIGINAL     String line = readTestFile.readLine();
// Should be
                String line = readValues.readLine();
                if (line == null) {
                    break;
                }
                
// ORIGINAL parse like this is not appropriate              
//              assert line.length() == 11;
//              String start = line.substring(0, 5);
//              String goal = line.substring(6, 11);
                // Use something like 
                 String [] tokens = line.split("[\s']");
                 
                 String start = tokens[0];
                 String goal = tokens[1];
                 
                BreadthFirstPaths bfs = new BreadthFirstPaths(g, words.indexOf(start));
                if (bfs.hasPathTo(words.indexOf(goal))) {
// Captions added for clarity                   
                    System.out.println("Distance : " + bfs.distTo(words.indexOf(goal)));
                    for (int v : bfs.pathTo(words.indexOf(goal))) {
                        System.out.print(" -> " + v);
                    }
                    System.out.println();
                } else
                    System.out.println("Nothing");
            }
        }
    }

}

请注意对

的修改

// ORIGINAL lines.

上面的代码产生

Distance : 1
 -> 0 -> 1
Distance : 1
 -> 0 -> 2
Distance : 1
 -> 3 -> 2

为什么在使用 BFS 时我的单词没有在 Undirected/Unweighted 图表中连接？

Why aren't my Words connecting in Undirected/Unweighted Graph when using BFS?

java

graph

breadth-first-search