java中应用dfs应使用arraydeque而非stack，因其性能更优、语义更清晰；节点需在出栈时标记visited以避免漏路径；栈模拟需逆序压入邻接点以匹配递归顺序；树可省略visited但无向图须防伪环。
用 Stack 还是 Deque 实现 DFS？
Java 里真正该用的不是 Stack 类，而是 ArrayDeque。因为 Stack 继承自过时的 Vector，同步开销大、性能差，且 push/pop 方法语义不如 Deque 的 push/pop 或 addFirst/removeFirst 清晰。
-
Stack是线程安全但慢，实际算法中根本不需要同步 -
ArrayDeque是非线程安全、数组-backed、扩容高效，push/pop均摊 O(1) - JDK 文档明确建议用
Deque替代Stack
示例写法：
Deque<Integer> stack = new ArrayDeque<>();<br>stack.push(start);
DFS 遍历图时怎么避免重复访问？
核心是维护一个 visited 数组或 Set，但关键在「什么时候标记」——必须在节点出栈（即开始处理）时标记，而不是入栈时。否则可能漏掉多条路径到达同一节点的情况（尤其在有向图或权值不等场景下）。
- 入栈时不标记：允许同一节点被多次压入（比如不同路径抵达），符合 DFS 探索逻辑
- 出栈时立即标记
visited[node] = true，然后才处理邻居 - 对每个邻居，只压入未访问过的（即
!visited[neighbor]） - 用
boolean[]比HashSet快，索引连续时优先选数组
递归 DFS 和栈模拟 DFS 行为一致吗？
不完全一致。递归版本天然按函数调用栈顺序回溯，而手写栈容易忽略「边访问边压入」的顺序细节，导致遍历顺序不同（比如邻接点压入顺序反了）。
立即学习“Java免费学习笔记（深入）”；
- 递归 DFS 访问
v后，按邻接表顺序依次对每个未访问邻居调用自身 - 栈模拟必须保证：对当前节点的每个邻居，按「逆序」压入栈（才能让第一个邻居最先弹出）
- 例如邻接列表是
[2, 3, 4]，应依次push(4),push(3),push(2) - 否则顺序会颠倒，影响调试和结果可预测性
常见错误现象：Stack 模拟出来的访问序列和递归版不一致，十有八九是压栈顺序没反过来。
树 vs 图：用栈做 DFS 时初始化差异在哪？
树没有环，不需要 visited 结构；图必须加，否则无限循环。但很多人忽略树也可能出现“伪环”——比如无向图存成双向邻接表，不记录父节点就会回头。
- 纯树（已知根、有向无环）：只需栈 + 当前节点，无需
visited - 无向图 / 可能含环的有向图：必须用
visited数组或集合 - 若用邻接表表示无向图，推荐在压栈时传入父节点 ID，跳过父节点即可避免回头，比
visited更轻量 -
visited初始化大小要够：图节点编号从 0 开始就用new boolean[n]，别用new boolean[n + 1]然后从 1 开始——容易越界或漏判
容易被忽略的是：哪怕你确定是树，只要输入是邻接表且未指定方向，就得按图处理。边界情况比想象中更常出现。
