我有一个具有以下格式的文件：
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，从属深度是$ 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
时间限制（70s和85s，是的-绝对是多余的）和深度限制是为了避免我的cgi-script超时。
如果我以足够的“深度”调用这两个例程，则可以看到它们是否连接，但是有很多死角。
我认为我正在进行广度优先搜索，而我认为应该进行深度优先搜索并丢弃未到达目标节点的搜索。
题：
给定一个开始节点和一个结束节点，是否存在一种有效的搜索算法，该算法将返回最少的节点以建立连接，或者返回某个值指示未找到路径？
此问题从Recursive function in PHP to find path between arbitrary nodes开始。我有通向目标节点（现在是目标节点）的节点，但是现在我想将其修剪为2个节点之间的路径。
编辑：我肯定答案已经在SO上了，但是我对PHP和这些算法来说还是很新的，所以还没有找到一个。
参考方案
像这样的结构会更好：
$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"]
假定以下函数并调用：function doSomething( &$someArray ) { // Do something to $someArray } $names=array("John", "Paul", "George", "Ringo"); doSomet…
PHP-如何建议搜索字词，“你是说……？” - php当使用不检索任何结果的术语搜索数据库时，我想允许“您是不是……”建议（例如Google）。例如，如果有人寻找“ jquyer””，它将输出“ did you mean jquery?”当然，建议结果必须与数据库内部的值匹配（我正在使用mysql）。您知道可以做到这一点的图书馆吗？我已经用谷歌搜索过，但是没有找到任何好的结果。或者，也许您有一个想法，该如何独自…
PHP-MySQL结果转换为JSON - php我试图了解如何将MySQL结果转换为JSON格式，以便以后可以在Javascript中使用此JSON来构建HTML表。但是我的代码只是产生大量的空值，我还不明白为什么。$result = mysqli_query($con, "SELECT * FROM Customers"); $test = json_encode($result);…
PHP Count数组元素 - php嗨，有人可以解释为什么这会返回“数组由0个元素组成”。 ：$arr = array(1,3,5); $count = count($arr); if ($count = 0) { echo "An array is empty."; } else { echo "An array has $count elements.…
PHP:从函数返回值并直接回显它？ - php这可能是一个愚蠢的问题，但是……的PHPfunction get_info() { $something = "test"; return $something; } html<div class="test"><?php echo get_info(); ?></div> 有没有办…