深度优先搜索(dfs)是一种算法,用于递归地遍历树或图数据,先向下遍历当前节点的所有子节点,然后返回到父节点并继续遍历。使用 php 递归函数实现 dfs 的步骤如下:标记节点已访问。打印节点。遍历子节点。
使用 PHP 递归函数实现深度优先搜索(DFS)
深度优先搜索(DFS)是一种用于遍历树或图数据的算法。它以当前节点开始,递归地向下遍历其所有可访问的子节点,然后再返回到其父节点并继续遍历。
使用 PHP 递归函数实现 DFS 如下:
function dfs($graph, $node) {
// 标记节点已访问
$graph[$node]['visited'] = true;
// 打印节点
echo $node . "n";
// 遍历子节点
foreach ($graph[$node]['children'] as $child) {
if (!$graph[$child]['visited']) {
dfs($graph, $child);
}
}
}
// 实战案例
$graph = [
'A' => ['children' => ['B', 'C']],
'B' => ['children' => ['D', 'E']],
'C' => ['children' => ['F', 'G']],
'D' => ['children' => []],
'E' => ['children' => []],
'F' => ['children' => []],
'G' => ['children' => []],
];
dfs($graph, 'A');