查找数据树节点之间路径的高效代码

Question

我有一个格式如下的文件：Y1DP480P T FDVII005 ID=000Y1DPMS7M T Y1DP480P ID=000Y1DPMS7M T Y1DP4860 ID=000Y1DPMS7M T Y1ENDCYP ID=000Y1DPMS6M T Y1DPMS7M ID=000Y1DPMS5M T VPY1CM28 ID=000Y1DPMS5M T Y1DPMS6M ID=000Y1DPAS21 T Y1DPMS5M ID=000Y1DPMS4M T FDRBC004 ID=000Y1DPMS4M T FDYBL004 ID=000等等等等仅使用第 1-8 列和第 12-19 列中的数据，可以认为是：node1 -> node2node1 -> node3node3 -> node5node2 -> node4node4 -> node5node5 -> node7我需要一种有效的方法来映射从给定起始节点到给定结束节点的路径。例如，如果我想要从 node1 到 node7 的路径，该函数将返回 node1->node3、node3->node5、node5->node7。目前的做法：我将文件读入一个数组，将前 19 个字符作为键和值，例如$data[Y1DP480P T FDVII005] = 'Y1DP480P T FDVII005'  （我使用该值作为键，因为输入文件可能包含重复项，因为这会将它们过滤掉——我认为 PHP 没有“设置”数据结构）。我有一个递归子例程，可以从给定节点中找到下一个“n”个依赖项，如下所示：（入口时，$path[] 是一个空数组，节点数据在 $data 中，开始搜索的节点是 $job，依赖的深度是 $depth）function createPathFrom($data, $job, $depth) {    global $path, $maxDepth, $timeStart;    $job = trim($job);    // echo "Looking for $job\n";    if ( $depth > $maxDepth ) {return;} // Search depth exceeded    // if ( (microtime(true) - $timeStart) > 70 ) {return;} //Might not be needed as we have the same further down    // $depth += 1;    // Get the initial list of predecessors for this job.    // echo __FUNCTION__."New iteration at depth $depth for $job\n";    $dependents = array_filter($data, function($dataLine) use($job){        // preg_match('/'.JOB_SPLIT_MASK.'/', $dataLine, $result);        // $dependent = trim($result[1]);        $dependent = explode(" ", $dataLine)[0];        return ( $dependent == $job );        // return ( preg_match('/'.$job.'/', $dependent) );    });我有一个几乎相同的功能，它为我的端节点建立了前辈，称为createPathTo时间限制（70 秒和 85 秒，是的 - 一个绝对是多余的）和深度限制是为了避免我的 cgi 脚本超时。如果我以足够的“深度”调用这两个例程，我可以查看它们是否连接，但有很多死胡同。我认为我正在进行广度优先搜索，而我认为我应该进行深度优先搜索并丢弃未到达目标节点的搜索。问题：给定一个开始节点和一个结束节点，是否有高效的搜索算法将返回最少的节点以建立连接或指示未找到路径的某个值？这个问题从PHP 中的 Recursive function 开始，以查找任意节点之间的路径。我有通向（现在来自）我的目标节点的节点，但现在我想将其修剪为仅 2 个节点之间的路径。编辑：我确定答案已经在这里了，但是我对 PHP 和这些算法很陌生，所以一直找不到。

Answer 1

使用这样的结构会更好：

$data =[

    "Y1DP480P" => ["FDVII005" => true],

    "Y1DPMS7M" => ["Y1DP480P" => true, "Y1DP4860" => true, "Y1ENDCYP" => true],

    // ...etc

];

因此，每个键都有一组子键，可以从第一个键开始一步到达。尽管集合不存在，但您通常会这样模仿：使用带有true值的关联数组（或者您喜欢的任何东西）。这也将忽略您在输入中可能存在的重复条目。

然后，标准的 BFS 将非常有效：

$input = "aaaaaaaa T bbbbbbbb ID=000

aaaaaaaa T cccccccc ID=000

cccccccc T eeeeeeee ID=000

bbbbbbbb T dddddddd ID=000

dddddddd T eeeeeeee ID=000

eeeeeeee T gggggggg ID=000";

// Convert input to the data structure:

$data = [];

foreach (explode("\n", $input) as $line) {

    list($a, $b) = explode(" T ", substr($line, 0, 19));

    $data[$a][$b] = true;

    if (!isset($data[$b])) $data[$b] = [];

}

function shortestPath($data, $source, $target) { // Perform a BFS

    $comeFrom[$source] = null;

    $frontier = [$source];

    while (count($frontier)) {

        $nextFrontier = [];

        foreach ($frontier as $key) {

            if ($key == $target) {

                $path = [];

                while ($key) { // unwind the comeFrom info into a path

                    $path[] = $key;

                    $key = $comeFrom[$key];

                }

                return array_reverse($path); // the path needs to go from source to target

            }

            foreach ($data[$key] as $neighbor => $_) {

                if (isset($comeFrom[$neighbor])) continue;

                $comeFrom[$neighbor] = $key;

                $nextFrontier[] = $neighbor;

            }

        }

        $frontier = $nextFrontier;

    }

}

$path = shortestPath($data, "aaaaaaaa", "gggggggg");

print_r($path); // ["aaaaaaaa", "cccccccc", "eeeeeeee", "gggggg"]