PHP 在多维数组中查找路径

Question

假设我们有一个数组，其中包含许多数组，用于定义特定节点的路径。例如：

X1     X3     X5     
|      |      |      
A  --  B  --  C  --  D
|      |      |      
X2     X4     X6     

并带有代码：

$array = [
'A' => ['B','X1','X2'],
'B' => ['C','X3','X4'],
'C' => ['D','X5','X6'],
];

找到最多 2 个节点的从一个点到另一个点的路径的最佳方法是什么？例如，要从A跳到D，您需要从A跳到B再到C，然后跳到D。

现在我已经编写了一个执行此搜索的函数，但我确信有更好的方法来执行此搜索(可能是递归搜索)。

private function findpath($array, $start, $end)
{
$result = array();
foreach ($array[$start] as $key1 => $value1) {
foreach ($array[$value1] as $key2 => $value2) {
if (in_array($end, $array[$value2])) {
return $result = [$start, $value1, $value2, $end];
}
}
}
} 
findpath($array, 'A', 'D');
// returns
// array:4 [
// 0 => "A"
// 1 => "B"
// 2 => "C"
// 3 => "D"
// ] 

Answer 1

一种可能的方法是使用堆栈作为要检查的路径列表。在循环中，您可以从堆栈中删除路径，检查它是否已找到目标，如果没有，则通过在节点$array中查找后续步骤来生成新路径，然后将新路径添加到堆栈中，以供循环的下一次迭代检查。如果堆栈变为空，则意味着找不到从头到尾的路径。

您提供的原始$array不允许路径循环或重复，但出于测试目的，我扩展了您的阵列，假设所有节点都完全连接：

$array = [
'A' => ['B','X1','X2'],
'B' => ['A', 'C','X3','X4'],
'C' => ['B', 'D','X5','X6'],
'D' => ['C'],
'X1' => ['A'],
'X2' => ['A'],
'X3' => ['B'],
'X4' => ['B'],
'X5' => ['C'],
'X6' => ['C'],
];

鉴于此，维护一个已访问过的节点的单独列表也是一个好主意，这样代码就不会重新访问节点或卡在循环路径中。

此函数将找到两个节点之间的最短路径，或者返回 false 找不到路径(使用 php 5.6 进行测试)：

function findpath(array $array, $start, $end, $steps = null)
{
$visited = []; // keep track of nodes already visited to avoid loops
$paths = [[$start]]; // array of paths to be checked
while ($path = array_pop($paths)) {
$node = end($path);
if ($node === $end) {
return $path; // found path from start to end node
}
if ($steps !== null && count($path) > $steps) {
continue; // path too long
}
$visited[$node] = true;
if (empty($array[$node])) {
continue; // can't reach any other nodes from this path
}
foreach ($array[$node] as $next) {
if (isset($visited[$next])) {
continue; // already visited next node
}
// make new path by adding next node to current path
// then add new path to array of paths to be checked
$paths[] = array_merge($path, [$next]);
}
}
return false; // no paths left to check, cannot find path from start to end node
}

您可以选择为函数提供最大步骤数(例如，路径A -> B -> C -> D为 3 步)：

var_dump(findPath($array, 'A', 'D', 3));
// returns ['A', 'B', 'C', 'D']
var_dump(findPath($array, 'A', 'D', 2));
// returns false as path would be longer than 2 steps
var_dump(findPath($array, 'X1', 'X6'));
// returns ['X1', 'A', 'B', 'C', 'X6']