本文详解如何在基于邻接表（ArrayList）表示的有向图中正确实现非递归深度优先搜索，重点解决因忽略访问状态检查导致的漏访问、死循环等问题，并提供可运行的健壮代码示例。
本文详解如何在基于邻接表（arraylist
深度优先搜索（DFS）是有向图遍历的核心算法之一，其核心思想是“一路走到底，回溯再探”。在使用栈实现的迭代版本中，关键约束在于：仅将未访问过的邻接顶点压入栈——而原代码中错误地在未判断 next.wasVisited 的前提下直接设为 true 并入栈，导致已访问节点被重复处理、后续节点无法抵达（如节点 3 未被访问），甚至可能引发无限循环（当存在环且无访问控制时）。
下面是一个结构清晰、生产可用的 Java DFS 迭代实现：
import java.util.*;
// 图中顶点定义
class Vertex {
String data;
boolean wasVisited;
public Vertex(String data) {
this.data = data;
this.wasVisited = false;
}
}
public class DirectedGraph {
private final ArrayList<linkedlist>> graph;
public DirectedGraph() {
this.graph = new ArrayList();
}
// 添加顶点（按索引顺序添加，假设顶点0,1,2...依次加入）
public void addVertex(Vertex v) {
LinkedList<vertex> adjList = new LinkedList();
adjList.add(v); // 首位存储自身标识（如 graph[i].get(0) 表示顶点i）
graph.add(adjList);
}
// 添加有向边 u → v（u 和 v 为顶点索引）
public void addEdge(int u, int v) {
if (u = graph.size() || v = graph.size()) {
throw new IllegalArgumentException("Invalid vertex index");
}
// graph[u] 对应顶点u的邻接表；跳过首元素（自身标识），追加邻接点v
graph.get(u).add(graph.get(v).get(0));
}
// 核心：迭代式 DFS（从指定顶点开始）
public void dfs(Vertex start) {
Stack<vertex> stack = new Stack();
// 初始化访问状态（建议在调用前统一重置，或此处显式重置全图）
resetVisited();
stack.push(start);
start.wasVisited = true;
while (!stack.isEmpty()) {
Vertex current = stack.pop();
System.out.print(current.data + " ");
// 遍历 current 的所有邻接顶点（即 graph 中对应顶点的邻接表，跳过首元素）
int idx = graph.indexOf(
graph.stream().filter(list -> !list.isEmpty() && list.get(0) == current)
.findFirst().orElse(null)
);
if (idx == -1) continue;
LinkedList<vertex> neighbors = graph.get(idx);
// 从索引1开始：neighbors.get(0) 是自身，neighbors.get(1..n) 是出边目标
for (int i = 1; i list : graph) {
for (Vertex v : list) {
if (v != null) v.wasVisited = false;
}
}
}
// 示例用法（构造题干所述图：0→2, 2→4, 4→5, 5→1, 1→3）
public static void main(String[] args) {
DirectedGraph g = new DirectedGraph();
// 创建顶点 0~5
for (int i = 0; i <p>✅ <strong>关键修正与最佳实践总结：</strong> </p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill3430" title="Alibabacloud Sdk Client Initialization For Java"><img
src="https://img.php.cn/upload/skill/000/000/081/178955835420587.jpg" alt="Alibabacloud Sdk Client Initialization For Java" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill3430" title="Alibabacloud Sdk Client Initialization For Java" class="overflowclass">Alibabacloud Sdk Client Initialization For Java</a>
<p class="overflowclass">在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。</p>
</div>
<a rel="nofollow" href="/xiazai/skill3430" title="Alibabacloud Sdk Client Initialization For Java" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<ul>
<li>
<strong>必须检查 <code>!next.wasVisited</code> 再入栈</strong>：这是避免重复访问、死循环和遗漏的根本保障； </li>
<li>
<strong>邻接表结构需明确语义</strong>：若 <code>graph[i].get(0)</code> 表示顶点 <code>i</code> 自身，则遍历时应从索引 <code>1</code> 开始读取邻接点； </li>
<li>
<strong>访问状态初始化要可靠</strong>：每次 DFS 前建议调用 <code>resetVisited()</code>，避免跨调用污染； </li>
<li>
<strong>推荐使用 <code>HashMap<vertex boolean></vertex></code> 或独立 <code>boolean[] visited</code> 数组替代 <code>Vertex.wasVisited</code> 字段</strong>，以解耦状态与数据，提升线程安全性与复用性（尤其在多算法共存场景）； </li>
<li>若需记录遍历路径或支持多起点，可扩展返回 <code>List<string></string></code> 而非仅打印。</li>
</ul>
<p>该实现严格遵循 DFS 迭代逻辑，输出与预期一致（<code>0 2 4 5 1 3</code>），具备健壮性、可读性与工程实用性。</p></vertex></vertex></vertex></linkedlist>Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
