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

Question

我有一个格式如下的文件:

Y1DP480P T FDVII005 ID=000
Y1DPMS7M T Y1DP480P ID=000
Y1DPMS7M T Y1DP4860 ID=000
Y1DPMS7M T Y1ENDCYP ID=000
Y1DPMS6M T Y1DPMS7M ID=000
Y1DPMS5M T VPY1CM28 ID=000
Y1DPMS5M T Y1DPMS6M ID=000
Y1DPAS21 T Y1DPMS5M ID=000
Y1DPMS4M T FDRBC004 ID=000
Y1DPMS4M T FDYBL004 ID=000

等等等

只使用了1-8和12-19列的数据，可以认为是:

node1 -> node2
node1 -> node3
node3 -> node5
node2 -> node4
node4 -> node5
node5 -> node7

我需要一种有效的方法来映射从给定起始节点到给定结束节点的路径。

例如，如果我想要从 node1 到 node7 的路径，该函数将返回 node1->node3，node3->node5，node5->node7。

当前方法:

我将文件读入一个数组，将前 19 个字符作为键和值，例如

$data[Y1DP480P T FDVII005] = 'Y1DP480P T FDVII005'  

(我使用该值作为键，因为输入文件可能包含重复项，因为这会过滤掉它们 - 我认为 PHP 没有“集合”数据结构)。

我有一个递归子例程，它从给定节点中找到下一个“n”个依赖项，如下所示:

(入口时，$path[]为空数组，节点数据在$data中，开始搜索的节点为$job，dependents的深度为$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) );
    });

    if (count($dependents) == 0) {
        return;
    } else {
        // print_r($predecessors);
        $elapsedTime = microtime(true) - $timeStart;
        // print $elapsedTime." : Searching ".count($dependents)." at depth ".$depth.NL;

        $path = array_merge($path, $dependents);
        foreach($dependents as $dependency) {
            // preg_match('/'.JOB_SPLIT_MASK.'/', $dependency, $result);
            // $dependent = trim($result[3]);
            $dependent = explode(" ", $dependency)[2];
            if ( (microtime(true) - $timeStart) > 85 ) {return;} // Let's get out if running out of time... (90s in HTTPD/conf)
            createPathFrom($data, $dependent, $depth+1);
        }
    }
}

我有一个几乎相同的函数，它为我的端节点建立了前身，称为 createPathTo

时间限制(70 秒和 85 秒，是的 - 一个绝对是多余的)和深度限制是为了避免我的 cgi 脚本超时。

如果我以足够的“深度”调用这两个例程，我可以看到它们是否连接，但是有很多死胡同。

我认为我正在进行广度优先搜索，而我认为我应该进行深度优先搜索并丢弃未到达目标节点的搜索。

问题:

给定一个起始节点和一个结束节点，是否有一种有效的搜索算法可以返回建立连接的最少节点数或一些表明未找到路径的值？

这个问题来自 Recursive function in PHP to find path between arbitrary nodes .我有通往(现在来自)我的目标节点的节点，但现在我想将其修剪为仅在 2 个节点之间的路径。

编辑:我确定答案已经在 SO 上了，但我对 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"]