修复图计算路径查找函数：解决双向路径查询失效问题

节点关系图 #

节点数据 #

$nodes = [
    'f' => ['d g'],
    'b' => ['a d'],
    'g' => ['i'],
    'd' => ['c e'],
    'i' => ['h']
];

原问题函数 #

以下是用于查找两个指定节点之间中间节点的函数，但存在部分测试用例无法正常返回结果的问题：

function findPathBetweenNodes($start, $end, $nodes) {
        
    foreach ($nodes as $node => $edges) {
        $nodes[$node] = explode(' ', $edges[0]);
    }

    function searchPath($current, $end, $nodes, &$visited) {
        if ($current === $end) {
            return [$current];
        }
        
        $visited[$current] = true;
        foreach ($nodes as $node => $children) {
            if (in_array($current, $children) && !isset($visited[$node])) {
                $path = searchPath($node, $end, $nodes, $visited);
                if ($path) {
                    return array_merge([$current], $path);
                }
            }
        }
        return null;
    }

    $visited = [];
    $path = searchPath($start, $end, $nodes, $visited);

    if ($path) {
        array_shift($path); 
        array_pop($path);   
    }

    return $path ?: []; 
}

测试用例及问题 #

• 测试用例1：print_r(findPathBetweenNodes('h', 'f', $nodes));
  返回正确结果：

  Array
  (
      [0] => i
      [1] => g
  )
  

• 测试用例2：print_r(findPathBetweenNodes('f', 'h', $nodes));
  返回空数组（预期应为['g', 'i']）
• 测试用例3：print_r(findPathBetweenNodes('a', 'c', $nodes));
  返回空数组（预期应为['b', 'd']）

问题分析与修复 #

原函数的核心问题在于searchPath方法的遍历逻辑是反向查找父节点：它遍历所有节点，寻找把当前节点作为子节点的父节点，这种逻辑只能处理从子节点到父节点的路径（比如测试用例1的h→i→g→f），但无法处理正向路径（f→g→i→h）或跨节点的路径（a→b→d→c）。

修复方案需要调整遍历逻辑，改为支持双向搜索，同时处理节点不存在于$nodes键中的情况（比如a节点，它是b的子节点但自身不是$nodes的键）：

修复后的完整函数 #

function findPathBetweenNodes($start, $end, $nodes) {
    // 预处理节点数据，将字符串转为子节点数组
    foreach ($nodes as $node => $edges) {
        $nodes[$node] = explode(' ', $edges[0]);
    }

    // 构建反向映射：子节点到父节点的关联，处理仅作为子节点存在的节点
    $reverseMap = [];
    foreach ($nodes as $parent => $children) {
        foreach ($children as $child) {
            $reverseMap[$child][] = $parent;
        }
    }

    function searchPath($current, $end, $nodes, $reverseMap, &$visited) {
        if ($current === $end) {
            return [$current];
        }
        
        $visited[$current] = true;
        
        // 先尝试正向查找当前节点的子节点
        if (isset($nodes[$current])) {
            foreach ($nodes[$current] as $child) {
                if (!isset($visited[$child])) {
                    $path = searchPath($child, $end, $nodes, $reverseMap, $visited);
                    if ($path) {
                        return array_merge([$current], $path);
                    }
                }
            }
        }
        
        // 再尝试反向查找当前节点的父节点
        if (isset($reverseMap[$current])) {
            foreach ($reverseMap[$current] as $parent) {
                if (!isset($visited[$parent])) {
                    $path = searchPath($parent, $end, $nodes, $reverseMap, $visited);
                    if ($path) {
                        return array_merge([$current], $path);
                    }
                }
            }
        }
        
        return null;
    }

    $visited = [];
    $path = searchPath($start, $end, $nodes, $reverseMap, $visited);

    if ($path) {
        array_shift($path); // 移除起始节点
        array_pop($path);   // 移除结束节点
    }

    return $path ?: []; 
}

修复说明 #

1. 构建反向映射表：新增$reverseMap，记录每个子节点对应的父节点，解决像a、c这类仅作为子节点存在的节点无法被遍历的问题。
2. 双向搜索逻辑：searchPath先尝试从当前节点的子节点正向搜索，再尝试从父节点反向搜索，确保无论路径方向如何都能被找到。
3. 边界处理：判断节点是否存在于$nodes或$reverseMap中，避免无意义的遍历。

验证修复结果 #

• 测试用例2返回：Array([0] => g, [1] => i)
• 测试用例3返回：Array([0] => b, [1] => d)
• 测试用例1仍返回正确结果

内容的提问来源于stack exchange，提问作者XTRUST.ORG