为什么我的广度优先搜索算法不能正确解决阶梯问题？

Question

我正在学习算法和数据结构课程，并且正在做一项作业，其中我必须使用广度优先搜索算法来解决字梯问题。它不起作用，我不知道为什么。对于某些单词，前几个单词是正确的，然后开始使用不是一个字母的单词。

代码：

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;

public class SENG300_Assignment13 {
    
    
    static Graph graph = new Graph();
    
    public static List<Vertex> adjustedBFS(Graph graph, Vertex startVertex, Vertex endVertex) {
        
          HashSet<Vertex> discoveredSet = new HashSet<Vertex>();
          Queue<Vertex> frontierQueue = new LinkedList<Vertex>();
          ArrayList<Vertex> visitedList = new ArrayList<Vertex>();
        
          // startVertex has a distance of 0 from itself
          //distances.put(startVertex, 0.0);
    
          frontierQueue.add(startVertex); // Enqueue startVertex in frontierQueue
          discoveredSet.add(startVertex); // Add startVertex to discoveredSet
          
          while (frontierQueue.size() > 0) {
              
             Vertex currentVertex = frontierQueue.remove();
             visitedList.add(currentVertex);
             
              if (currentVertex.equals(endVertex)) {
                  break;
              }
             
             for (Edge edge : graph.getEdgesFrom(currentVertex)) {
                Vertex adjacentVertex = edge.toVertex;
                
                if (!discoveredSet.contains(adjacentVertex)) {
                   frontierQueue.add(adjacentVertex);
                   discoveredSet.add(adjacentVertex);
                    
                   // Distance of adjacentVertex is 1 more than currentVertex
                   //distances.put(adjacentVertex, distances.get(currentVertex) + 1);
                }
             }
          }
          return visitedList;
       }
    
    public static void addEdgeForOneLetterApart(Graph graph) {
        List<Vertex> vertices = new ArrayList<>(graph.getVertices());
        
        for (int i = 0; i < vertices.size(); i++) {
            Vertex v1 = vertices.get(i);
            
            for (int j = 0; j < vertices.size(); j++) {
                Vertex v2 = vertices.get(j);
                
                if (areOneLetterApart(v1.getValue(), v2.getValue())) {
                    graph.addUndirectedEdge(v1, v2);
                    graph.addUndirectedEdge(v2, v1);
                }
            }
        }
    }
    
    public static boolean areOneLetterApart(String v1, String v2) {
        int differenceCount = 0;
        
        if (v1.length() != v2.length()) {
            return false;
        }
        
        for (int i = 0; i < v1.length(); i++) {
            if (v1.charAt(i) != v2.charAt(i)) {
                differenceCount++;
                
                if (differenceCount > 1) {
                    return false;
                }
            }
        }
        
        return differenceCount == 1;
        
    }
    
    

    // Driver code
    public static void main(String[] args) {
        Graph wordGraph = new Graph();
        FileInputStream fileByteStream = null;
        Scanner scnr = new Scanner(System.in);
        Scanner inFS = null;
        String word;
        int counter = 0;
        
        
        try {
            fileByteStream = new FileInputStream("words_alpha.txt");
            inFS = new Scanner(fileByteStream);
            
            while (inFS.hasNextLine()) {
                word = inFS.nextLine();
                
                graph.addVertex(word);
                
                counter++;
                
            }
            
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        
        
        
        Vertex start = new Vertex("wing");
        Vertex target = new Vertex("left");
        
        addEdgeForOneLetterApart(graph);
        
        System.out.println(adjustedBFS(graph, start, target));
    }
}

这是使用这些起始变量和目标变量时的输出列表： 【翼、风、酒、环、善、心、线、线、智、矿、宽、如、火、边、大小】

我真的不确定发生了什么事，任何帮助将不胜感激。谢谢你。

Answer 1

主要问题是

visitedList

是按广度优先顺序填充的，所以一般来说它不会代表路径。它包含所有访问过的节点，当然不能保证它们都位于最短路径上。

在您的示例图中，起始节点“wing”具有直接邻居“ring”、“wind”和“wine”，并且这些节点将在任何其他节点之前被访问，因为这就是广度优先所做的。我们可以立即看到这些节点如何最终出现在

visitedList

中，但它们并没有形成 path。只有其中一个会出现在路上，但在你访问它们的那一刻，你还不知道这一点。只有当目标节点被访问过之后，才可以开始重构路径。

为了做到这一点，您需要记住您访问每个节点时来自哪里。一旦找到目标节点，这些信息就可以用来重建路径。从那里，您可以按照这些反向引用回到起始节点，并在执行此操作时重建路径。

其他一些备注：

• 不要使用静态

  graph

  字段。您在本地创建了

  wordGraph

  ，这很好，但是您从不使用它，而是使用静态字段。删除静态字段并仅适用于本地实例。

• 不能仅通过将 ArrayList 作为参数提供给

  System.out.println

  来打印它。相反，迭代列表并打印各个顶点。

• 正如名称

  addUndirectedEdge

  所示，此方法将创建一个 无向 边，因此不必调用它两次——如果它要创建一个 有向 边，您就需要调用它。但这取决于该方法的实际实现。由于您没有提供，请检查您是否需要调用两次或一次。

• 与上一点相关：如

  addEdgeForOneLetterApart

  中所示，您查看所有节点的所有邻居，无论如何，您都会以两种可能的顺序访问同一对节点，并对这两个节点调用

  graph.addUndirectedEdge

  。因此，您甚至可以限制内部循环以避免“双重”调用，并使其以

  for (int j = i + 1; ...

  开头

这是

adjustedBFS

的更正版本：

    public static List<Vertex> adjustedBFS(Graph graph, Vertex startVertex, Vertex endVertex) {
        // When discovering a node, track where we came from. Use a Map instead of Set:
        HashMap<Vertex, Vertex> discoveredLink = new HashMap<Vertex, Vertex>(); 
        Queue<Vertex> frontierQueue = new LinkedList<Vertex>();
        ArrayList<Vertex> visitedList = new ArrayList<Vertex>();
        
        frontierQueue.add(startVertex);
        discoveredLink.put(startVertex, null); // Start-vertex has no predecessor 
        
        while (frontierQueue.size() > 0) {
            Vertex currentVertex = frontierQueue.remove();
            // We don't know if this vertex will be on the path,
            //    so don't add it to visitedList yet
            if (currentVertex.equals(endVertex)) {
                // Reconstruct the path
                while (currentVertex != null) {
                    visitedList.add(currentVertex);
                    currentVertex = discoveredLink.get(currentVertex);
                }
                // As we started from the end vertex, we need to reverse:
                Collections.reverse(visitedList);
                break;
            }
            for (Edge edge : graph.getEdgesFrom(currentVertex)) {
                Vertex adjacentVertex = edge.toVertex;

                if (!discoveredLink.containsKey(adjacentVertex)) {
                    frontierQueue.add(adjacentVertex);
                    discoveredLink.put(adjacentVertex, currentVertex); // remember predecessor
                }
            }
        }
        return visitedList;
    }

Answer 2

function ladderLength(beginWord, endWord, wordList) {
if (!wordList.includes(endWord)) {
    return 0;
}

let queue = [[beginWord, 1]];
let visited = new Set([beginWord]);

while (queue.length > 0) {
    let [word, depth] = queue.shift();
    
    if (word === endWord) {
        return depth;
    }
    
    for (let i = 0; i < word.length; i++) {
        let newWord = '';
        
        for (let j = 0; j < word.length; j++) {
            newWord += (j === i) ? '_' : word[j];
        }
        
        for (let c = 97; c <= 122; c++) {
            let nextWord = newWord.replace('_', String.fromCharCode(c));
            
            if (wordList.includes(nextWord) && !visited.has(nextWord)) {
                visited.add(nextWord);
                queue.push([nextWord, depth + 1]);
            }
        }
    }
}

return 0;

}