向数组添加Node类对象问题：#find_knight_path输出final_path时无限循环

我写了一个find_knight_path函数用于骑士巡游问题，现在遇到一个问题：函数里的puts语句能正常运行，但只要尝试输出final_path数组或者打印函数返回值，控制台就会陷入无限循环。我暂时找不到原因，虽然知道代码需要优化，但先想解决这个循环问题。以下是函数代码：

def find_knight_path(graph, start_pos, end_pos)
    queue = []
    final_path = []
    distance = 0
    predecessor = nil
    pos_start = graph.nodes[start_pos]
    pos_start.distance = 0
    pos_start.predecessor = nil
    queue.push(pos_start)
    final_path.push(pos_start)
    
    while !queue.empty?
      current_item = queue.shift
      # puts "line 97 - What is current_item.value? #{current_item.value}"
      distance += distance
      predecessor = current_item
      current_item.adjacent_nodes.each do |i|
        i.distance = distance
        i.predecessor = predecessor
        queue.push(i) 
      end
      puts "final_path value - #{current_item}"
      puts "final_path length - #{final_path.length}"
      final_path.push(current_item)
      # p "final_path #{final_path}"
      # p "queue #{queue}"
      return final_path.reverse if current_item.value == end_pos
      # puts "final_path length #{final_path.length}"
    end
    final_path.reverse
end

问题根源分析 #

1. 对象循环引用导致输出无限递归
   你在final_path中存储的是完整的Node对象，当用p或直接打印数组时，Ruby会递归输出对象的所有属性（包括adjacent_nodes）。而邻接节点又会引用回其他已遍历的节点，形成循环引用链，导致输出时无限遍历对象属性，看起来像是程序陷入无限循环。

2. BFS逻辑缺陷导致队列无限增长

   • distance += distance是错误的：第一次执行后distance会变成0，之后永远保持0，无法正确记录路径层级。
   • 没有节点去重机制：同一个节点会被多次加入队列，导致队列永远不会为空，最终触发真正的无限循环（之前用puts输出单个节点时未暴露）。
   • final_path构建逻辑错误：当前代码是把所有遍历过的节点都加入数组，这不是从起点到终点的有效路径，而是遍历过的节点集合。

解决步骤 #

1. 解决输出时的无限递归问题

不要直接输出Node对象数组，而是提取节点的value属性输出，避免递归遍历对象引用：

# 替换原输出语句
p "final_path #{final_path.map(&:value)}"

2. 修复BFS核心逻辑，避免队列无限增长

• 添加已访问节点标记，防止重复入队
• 修正路径长度计算方式
• 改为通过predecessor回溯构建有效路径

修正后的示例代码：

def find_knight_path(graph, start_pos, end_pos)
  queue = []
  visited = Set.new # 用集合记录已访问的节点坐标
  pos_start = graph.nodes[start_pos]
  pos_start.distance = 0
  pos_start.predecessor = nil
  queue.push(pos_start)
  visited.add(pos_start.value)

  while !queue.empty?
    current_item = queue.shift

    # 找到目标节点，通过predecessor回溯构建路径
    if current_item.value == end_pos
      final_path = []
      current = current_item
      while current
        final_path << current.value
        current = current.predecessor
      end
      return final_path.reverse
    end

    current_item.adjacent_nodes.each do |i|
      next if visited.include?(i.value) # 跳过已访问节点
      i.distance = current_item.distance + 1 # 基于当前节点距离+1
      i.predecessor = current_item
      queue.push(i)
      visited.add(i.value)
    end
  end

  # 未找到路径时返回空数组
  []
end

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