php中dfs通过递归或栈实现“一条路走到黑”，适用于树（如二叉树前序遍历）和图（需visited防环）；树可省visited，图必须标记；非递归版用array_push/array_pop模拟栈，入栈顺序影响遍历路径。
PHP 中实现深度优先遍历（DFS），核心是利用递归或栈模拟“一条路走到黑，回退再探”的逻辑。适用于树、图等结构，最常见的是二叉树遍历和邻接表表示的图。
二叉树的 DFS（递归方式）
这是最直观的实现，按“根→左→右”顺序访问（前序遍历），也属于 DFS 的一种典型体现：
- 先处理当前节点（如输出值、存入数组）
- 递归遍历左子树
- 递归遍历右子树
示例代码：
function dfsTree($node) {
if ($node === null) return;
echo $node->val . ' '; // 访问当前节点
dfsTree($node->left); // 深入左子树
dfsTree($node->right); // 深入右子树
}
图的 DFS（邻接表 + 递归/栈）
图可能有环，必须用 visited 数组标记已访问节点，避免死循环：
立即学习“PHP免费学习笔记（深入）”；
- 从起始顶点开始，标记为已访问
- 遍历其所有未访问的邻接点，对每个点递归调用 DFS
- 也可用显式栈替代递归（适合深图防栈溢出）
邻接表示例（关联数组）：
$graph = [
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
];
function dfsGraph($graph, $start, &$visited = []) {
$visited[$start] = true;
echo $start . ' ';
foreach ($graph[$start] as $neighbor) {
if (!isset($visited[$neighbor])) {
dfsGraph($graph, $neighbor, $visited);
}
}
}
dfsGraph($graph, 'A'); // 输出：A B D E F C
非递归 DFS（用栈手动管理）
用 PHP 的 array_push / array_pop 模拟栈，更清晰反映 DFS 执行过程，且可控性强：
- 初始化栈，压入起点
- 循环直到栈空：弹出一个节点，若未访问则标记并处理，再将其未访问邻接点压入栈（注意顺序影响遍历结果）
栈版图遍历示例：
function dfsStack($graph, $start) {
$visited = [];
$stack = [$start];
while (!empty($stack)) {
$node = array_pop($stack);
if (!isset($visited[$node])) {
$visited[$node] = true;
echo $node . ' ';
// 逆序压入，保证左邻接点先被处理（与递归一致）
$neighbors = array_reverse($graph[$node]);
foreach ($neighbors as $n) {
if (!isset($visited[$n])) {
array_push($stack, $n);
}
}
}
}
}
关键注意事项
实际使用时需注意几个易错点：
- 环检测必须做：图中无 visited 控制会无限递归或死循环
- 树 vs 图结构区别：树天然无环，图必须显式判重；树可省略 visited，图不可
- 栈顺序影响结果：非递归版中邻接点入栈顺序决定“优先往哪边深入”，例如正序入栈会导致右子树先被访问
- 内存与性能：递归简洁但深度大时可能爆栈；迭代版空间可控，适合大规模图
