17370845950

本文深入探讨了在java中使用广度优先搜索（bfs）算法计算无权图最短路径时可能遇到的问题。重点分析了原始实现中因路径映射错误导致的路径计算不准确问题，并提供了基于父节点回溯的正确bfs算法实现。文章还强调了java中自定义对象在哈希集合中使用时，正确重写equals()和hashcode()方法的重要性，以确保算法的健壮性和正确性。

BFS最短路径算法原理回顾

广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法。它从图的某个节点开始，然后逐层地访问其所有邻居节点，接着访问这些邻居节点的邻居，依此类推。在无权图中，BFS的一个关键特性是它总是能找到从源节点到目标节点的最短路径。这是因为BFS以“层”的方式扩展，第一次访问到任何节点时，其路径必然是最短的。

为了实现BFS并记录路径，我们需要以下核心组件：

• 队列（Queue）：用于存储待访问的节点，确保按层级顺序访问。
• 已访问集合/路径映射：用于记录哪些节点已被访问，避免重复访问和陷入死循环。同时，它也需要存储节点之间的父子关系，以便最终重建路径。

原代码问题分析

原始代码在尝试计算最短路径时，输出了错误的路径（例如 0 -> 2 -> 3 -> 4 -> 5 而非 0 -> 2 -> 3 -> 4 -> 6 -> 7）。其主要问题在于路径记录机制的缺陷：

1. 路径记录映射方向错误与覆盖问题： 原始代码使用 Map nextNodeMap 来记录 currentNode 到 nextNode 的映射。这种方式的问题在于，一个 currentNode 可能有多个 nextNode（即一个父节点有多个子节点）。当 nextNodeMap.put(currentNode, nextNode) 被调用多次时，currentNode 作为键的值会被反复覆盖。例如，如果 node4 既连接 node5 又连接 node6，先执行 nextNodeMap.put(node4, node5)，后执行 nextNodeMap.put(node4, node6)，那么 node4 -> node5 的路径信息就会被 node4 -> node6 覆盖，最终路径重建时可能无法回溯到正确的子节点，从而导致路径错误。

2. previousNode 变量的误用： 代码中引入了 previousNode 变量，并试图在找到目标节点时使用它来处理多分支情况。然而，这种逻辑未能正确地为每个节点建立唯一的父节点关系，使得路径重建的逻辑变得复杂且容易出错。

3. 冗余的 visitedNodes 集合： 当正确使用一个映射来记录节点及其父节点关系时（如 Map paths），这个映射本身就可以指示哪些节点已经被访问过（即 paths.containsKey(node)），因此单独的 visitedNodes HashSet 变得冗余。

BFS最短路径的正确实现

为了