Java中BFS算法无法正确计算最短路径的问题修复请求

我在Java中使用BFS算法计算从Node 0到Node 7的最短路径时，得到的结果是(0 -> 2 -> 3 -> 4 -> 5)，并未到达目标节点Node 7，需要排查并修复该问题。

问题代码 #

Node类 #

public class Node {
  private final int value;
  private final Set<Node> siblingNodes;

  public Node(int value) {
    this.value = value;
    siblingNodes = new HashSet<Node>();
  }

  public Set<Node> getSiblingNodes() {
    return siblingNodes;
  }

  public boolean equals(Node compareTo) {
    return (compareTo.getValue() == value);
  }

  public int getValue() {
    return value;
  }

  public void addSiblingNode(Node node) {
    siblingNodes.add(node); 
  }
}

主代码片段 #

public static void main(String[] args) {
    /**
     *
     *        1             -> 5
     * 0 ->           -> 4
     *        2 -> 3        -> 6    -> 7
     *
     */
        Node node0 = new Node(0);

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        node0.addSiblingNode(node1);
        node0.addSiblingNode(node2);    

        Node node3 = new Node(3);
        node2.addSiblingNode(node3);

        Node node4 = new Node(4);
        node3.addSiblingNode(node4);

        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node4.addSiblingNode(node5);
        node4.addSiblingNode(node6);
        
        Node node7 = new Node(7);
        node6.addSiblingNode(node7);

        List<Node> shortestPath = getDirections(node0, node7);
        for(Node node : shortestPath) {
          System.out.println(node.getValue());
        }
      }

      public static List<Node> getDirections(Node sourceNode, Node destinationNode) {
        // Initialization.
        Map<Node, Node> nextNodeMap = new HashMap<Node, Node>();
        Node currentNode = sourceNode;
        Node previousNode = sourceNode;

        // Queue
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(currentNode);

        Set<Node> visitedNodes = new HashSet<Node>();
        visitedNodes.add(currentNode);

        //Search.
        while (!queue.isEmpty()) {
          currentNode = queue.remove();
          if (currentNode.equals(destinationNode)) {
            if (!previousNode.equals(currentNode)) {
              nextNodeMap.put(previousNode, currentNode);
            }
            break;
          } else {
            for (Node nextNode : currentNode.getSiblingNodes()) {
              if (!visitedNodes.contains(nextNode)) {
                queue.add(nextNode);
                visitedNodes.add(nextNode);

                nextNodeMap.put(currentNode, nextNode);
                previousNode = currentNode;
              }
            }
          }
        }

        if (!currentNode.equals(destinationNode)) {
            throw new RuntimeException("No feasible path.");
        }

        List<Node> directions = new LinkedList<Node>();
        for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) {
            directions.add(node);
        }

        return directions;
      }

问题根源分析 #

1. Node类方法重写错误：未遵循Java规范重写equals(Object)和hashCode()，仅重载了equals(Node)方法，导致HashSet、HashMap等集合无法正确识别节点的逻辑相等性，可能引发异常判断。
2. 路径记录逻辑错误：使用nextNodeMap记录当前节点的子节点，当一个节点有多个子节点时，后续子节点会覆盖之前的记录，导致路径重建时走入错误分支，无法到达目标节点。

修复方案 #

1. 修正Node类的equals和hashCode方法 #

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Node {
    private final int value;
    private final Set<Node> siblingNodes;

    public Node(int value) {
        this.value = value;
        siblingNodes = new HashSet<>();
    }

    public Set<Node> getSiblingNodes() {
        return siblingNodes;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        return value == node.value;
    }

    @Override
    public int hashCode() {
        return Objects.hash(value);
    }

    public int getValue() {
        return value;
    }

    public void addSiblingNode(Node node) {
        siblingNodes.add(node);
    }
}

2. 修改BFS路径记录逻辑（使用父节点映射） #

import java.util.*;

public class BFSShortestPath {
    public static void main(String[] args) {
        /**
         *
         *        1             -> 5
         * 0 ->           -> 4
         *        2 -> 3        -> 6    -> 7
         *
         */
        Node node0 = new Node(0);

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        node0.addSiblingNode(node1);
        node0.addSiblingNode(node2);

        Node node3 = new Node(3);
        node2.addSiblingNode(node3);

        Node node4 = new Node(4);
        node3.addSiblingNode(node4);

        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node4.addSiblingNode(node5);
        node4.addSiblingNode(node6);

        Node node7 = new Node(7);
        node6.addSiblingNode(node7);

        List<Node> shortestPath = getDirections(node0, node7);
        for (Node node : shortestPath) {
            System.out.print(node.getValue() + (node != shortestPath.getLast() ? " -> " : ""));
        }
    }

    public static List<Node> getDirections(Node sourceNode, Node destinationNode) {
        // 记录每个节点的父节点，用于回溯路径
        Map<Node, Node> parentMap = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        Set<Node> visitedNodes = new HashSet<>();

        queue.add(sourceNode);
        visitedNodes.add(sourceNode);
        parentMap.put(sourceNode, null); // 源节点无父节点

        boolean found = false;
        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();
            if (currentNode.equals(destinationNode)) {
                found = true;
                break;
            }
            for (Node nextNode : currentNode.getSiblingNodes()) {
                if (!visitedNodes.contains(nextNode)) {
                    visitedNodes.add(nextNode);
                    parentMap.put(nextNode, currentNode);
                    queue.add(nextNode);
                }
            }
        }

        if (!found) {
            throw new RuntimeException("No feasible path.");
        }

        // 从目标节点回溯到源节点
        List<Node> path = new LinkedList<>();
        Node current = destinationNode;
        while (current != null) {
            path.add(current);
            current = parentMap.get(current);
        }
        // 反转路径得到源到目标的顺序
        Collections.reverse(path);
        return path;
    }
}

修复效果验证 #

运行修改后的代码，会正确输出从Node 0到Node 7的最短路径：0 -> 2 -> 3 -> 4 -> 6 -> 7。

内容的提问来源于stack exchange，提问作者Sercan Noyan Germiyanoğlu