BFS算法无法正确解决单词阶梯问题，寻求技术排查帮助

问题描述 #

修读算法与数据结构课程时，用BFS算法完成单词阶梯作业出现异常：部分单词前几步处理正确，但后续出现非单字母差异的单词。以下是代码、运行输出及问题分析。

原代码 #

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>();
        
          frontierQueue.add(startVertex); 
          discoveredSet.add(startVertex); 
          
          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);
                }
             }
          }
          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) {
            e.printStackTrace();
        }
        
        
        
        Vertex start = new Vertex("wing");
        Vertex target = new Vertex("left");
        
        addEdgeForOneLetterApart(graph);
        
        System.out.println(adjustedBFS(graph, start, target));
    }
}

异常输出 #

当起始单词为wing、目标单词为left时，输出列表为：

[wing, wind, wine, ring, kind, mind, line, wire, wise, mine, wide, like, fire, side, size]

问题分析 #

1. 核心错误：返回值不是路径而是所有访问节点
   你的adjustedBFS方法返回的是BFS遍历过程中所有访问过的节点列表，而非从起始到目标的单词阶梯路径。后续出现的非单字母差异单词，是BFS其他分支上的节点，并非路径的一部分。

2. 边添加重复且效率低下
   addEdgeForOneLetterApart方法中，双重循环从j=0开始，会重复处理同一对节点（比如i=0,j=1和i=1,j=0），且addUndirectedEdge本身就是双向边，调用两次会导致重复添加边，浪费内存和遍历时间。

3. 未使用局部变量wordGraph
   main方法中创建了wordGraph但全程未使用，一直操作静态的graph变量，虽然不影响功能，但不符合代码规范，易引发混淆。

修复方案 #

1. 修改BFS以记录并返回路径 #

给每个节点记录前驱，找到目标节点后回溯出路径：

public static List<Vertex> adjustedBFS(Graph graph, Vertex startVertex, Vertex endVertex) {
    HashSet<Vertex> discoveredSet = new HashSet<>();
    Queue<Vertex> frontierQueue = new LinkedList<>();
    HashMap<Vertex, Vertex> predecessors = new HashMap<>(); // 记录前驱节点

    frontierQueue.add(startVertex);
    discoveredSet.add(startVertex);
    predecessors.put(startVertex, null); // 起始节点无前驱

    while (!frontierQueue.isEmpty()) {
        Vertex currentVertex = frontierQueue.remove();

        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);
                predecessors.put(adjacentVertex, currentVertex); // 记录前驱
            }
        }
    }

    // 回溯构建路径
    List<Vertex> path = new ArrayList<>();
    Vertex current = endVertex;
    while (current != null) {
        path.add(current);
        current = predecessors.get(current);
    }
    Collections.reverse(path); // 反转得到从start到end的路径

    // 如果路径只有起始节点，说明无法到达目标
    return path.size() == 1 && !path.get(0).equals(endVertex) ? Collections.emptyList() : path;
}

2. 优化边添加逻辑 #

避免重复处理节点对，且只调用一次无向边添加：

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);
        // j从i+1开始，避免重复处理同一对节点
        for (int j = i + 1; j < vertices.size(); j++) {
            Vertex v2 = vertices.get(j);
            if (areOneLetterApart(v1.getValue(), v2.getValue())) {
                graph.addUndirectedEdge(v1, v2); // 无向边只需添加一次
            }
        }
    }
}

3. 修正main方法的变量使用 #

将静态graph替换为局部wordGraph，避免全局变量污染：

// 去掉静态graph变量
// static Graph graph = new Graph();

// Driver code
public static void main(String[] args) {
    Graph wordGraph = new Graph(); // 使用局部变量
    // ... 其他代码保持不变 ...
    while (inFS.hasNextLine()) {
        word = inFS.nextLine();
        wordGraph.addVertex(word); // 操作局部wordGraph
        counter++;
    }
    // ...
    addEdgeForOneLetterApart(wordGraph);
    System.out.println(adjustedBFS(wordGraph, start, target));
}

说明 #

修复后，adjustedBFS会返回从wing到left的最短单词阶梯路径（如果存在），而非所有访问过的节点，解决了后续出现非单字母差异单词的问题。

内容的提问来源于stack exchange，提问作者Evan Schulte