java中dfs遍历复杂图需稳住三件事：清晰的邻接表建图（支持不连续编号与非连通）、全局visited标记防环与重复访问、显式栈实现提升可控性；由此可自然扩展环检测、连通分量、拓扑排序等。
Java 中用深度优先搜索（DFS）遍历复杂图结构，关键不是堆砌技巧，而是稳住三件事：图的表示要清晰、访问状态要严格标记、递归或栈的控制逻辑要闭环。复杂图往往含环、非连通、顶点编号不连续、边方向不固定，这些都会让遍历出错——但只要基础框架扎实，都能应对。
用邻接表建图，兼容稀疏与非连通结构
复杂图通常边数远少于顶点数的平方，邻接表比邻接矩阵更省空间也更灵活。推荐用 Map<integer list>></integer> 或自定义 Graph 类封装：
- 键为顶点编号（支持不连续，如 101、205、999），值为邻居列表
- 添加边时双向处理（无向图）或单向（有向图），避免漏连
- 对非连通图，不能只从 0 开始搜一次；需外层遍历所有顶点，对每个未访问顶点启动一轮 DFS
必须用 visited 集合/数组精准控访问状态
环是复杂图中最常见的陷阱。仅靠“当前路径中是否出现”（如用递归栈判断）只能防环导致的死递归，但无法防止跨路径重复访问。正确做法是全局唯一标记：
- 顶点编号连续且范围已知 → 用
boolean[] visited = new boolean[n] - 编号稀疏或不确定 → 用
Set<integer> visited = new HashSet()</integer> - 切忌在递归内仅靠局部变量判断；每次进入新顶点前，先查 visited，再标记，再处理逻辑
递归写法简洁，但栈实现更可控
递归最贴近 DFS “一条路走到黑”的直觉，适合教学和中小规模图。但复杂图深度可能很大，易触发 StackOverflowError。生产环境建议显式用 Stack：
- 初始化：将起点入栈，并立即标记
visited.add(start) - 循环：弹出栈顶顶点 → 输出/处理 → 遍历其所有邻接点 → 对每个
!visited.contains(neighbor)的邻居，标记并入栈 - 注意：入栈顺序影响遍历序列（如想按编号升序访问邻居，需先排序再压栈）
遍历后能自然支撑常见扩展需求
一个健壮的 DFS 遍历骨架，稍加改造就能解决实际问题：
- 检测环：递归时额外维护
onStack标记当前路径上的节点，若访问邻居时发现它已在onStack中，即存在环 - 找连通分量：每启动一轮 DFS 就计数 +1，该轮访问到的所有顶点属于同一分量
- 拓扑排序（有向无环图）：按递归退出顺序（post-order）收集顶点，再逆序输出
- 路径查询：在 DFS 中维护
parent[]或路径列表，找到目标即返回
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
