1. 概述
在本教程中，我们将深入探讨 Java 中的 深度优先搜索（Depth-First Search, DFS）。
DFS 是一种用于 树（Tree） 和 图（Graph） 数据结构的遍历算法。它的核心思想是：在切换分支前，先尽可能深入地遍历当前分支的所有节点。
接下来我们将依次讲解：
- DFS 在树结构中的三种遍历方式
- DFS 在图结构中的实现
- 图的拓扑排序应用
如需了解树和图的 Java 实现，可以参考我们之前的文章：二叉树 和 图。
2. 树的深度优先搜索
使用 DFS 遍历树时，有三种常见的顺序：
- 前序遍历（Preorder Traversal）
- 中序遍历（Inorder Traversal）
- 后序遍历（Postorder Traversal）
2.1 前序遍历（Preorder Traversal）
前序遍历的顺序是：先访问根节点，然后是左子树，最后是右子树。
使用递归实现非常简单：
public void traversePreOrder(Node node) {
if (node != null) {
visit(node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}
也可以使用栈（Stack）实现非递归版本：
public void traversePreOrderWithoutRecursion() {
Stack<Node> stack = new Stack<>();
Node current = root;
stack.push(root);
while (!stack.isEmpty()) {
current = stack.pop();
visit(current.value);
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
✅ 小贴士：注意右子节点先入栈，这样左子节点会先被访问。
2.2 中序遍历（Inorder Traversal）
中序遍历的顺序是：先访问左子树，然后是根节点，最后是右子树。
对于二叉搜索树（BST），中序遍历会按升序输出节点值。
递归实现如下：
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
visit(node.value);
traverseInOrder(node.right);
}
}
非递归版本使用栈来模拟递归过程：
public void traverseInOrderWithoutRecursion() {
Stack<Node> stack = new Stack<>();
Node current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
Node top = stack.pop();
visit(top.value);
current = top.right;
}
}
2.3 后序遍历（Postorder Traversal）
后序遍历的顺序是：先访问左子树，然后是右子树，最后是根节点。
递归实现如下：
public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
visit(node.value);
}
}
非递归实现稍复杂，需要额外判断是否左右子节点都已处理：
public void traversePostOrderWithoutRecursion() {
Stack<Node> stack = new Stack<>();
Node prev = root;
Node current = root;
stack.push(root);
while (!stack.isEmpty()) {
current = stack.peek();
boolean hasChild = (current.left != null || current.right != null);
boolean isPrevLastChild = (prev == current.right ||
(prev == current.left && current.right == null));
if (!hasChild || isPrevLastChild) {
current = stack.pop();
visit(current.value);
prev = current;
} else {
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
}
⚠️ 注意：该实现使用了两个指针 current 和 prev 来判断是否所有子节点都已访问完毕。
3. 图的深度优先搜索
图和树的最大区别在于：图中可能包含环（Cycle）。
为了避免陷入无限循环，我们需要在访问每个节点时进行标记。
我们将展示两种图的 DFS 实现方式：递归和非递归。
3.1 图的递归 DFS
递归实现非常直观：
public boolean[] dfs(int start) {
boolean[] isVisited = new boolean[adjVertices.size()];
return dfsRecursive(start, isVisited);
}
private boolean[] dfsRecursive(int current, boolean[] isVisited) {
isVisited[current] = true;
visit(current);
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
dfsRecursive(dest, isVisited);
}
return isVisited;
}
3.2 图的非递归 DFS
使用栈实现非递归 DFS：
public void dfsWithoutRecursion(int start) {
Stack<Integer> stack = new Stack<>();
boolean[] isVisited = new boolean[adjVertices.size()];
stack.push(start);
while (!stack.isEmpty()) {
int current = stack.pop();
if (!isVisited[current]) {
isVisited[current] = true;
visit(current);
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
stack.push(dest);
}
}
}
}
✅ 小贴士：图的 DFS 与树的 DFS 原理一致，只是多了访问标记的处理。
3.3 拓扑排序（Topological Sort）
DFS 的一个经典应用是 拓扑排序，适用于 有向无环图（DAG）。
拓扑排序的结果是节点的一个线性顺序，满足：如果存在边 A → B，那么 A 在 B 之前。
实现方式是对每个节点递归访问完所有邻居后再入栈：
public List<Integer> topologicalSort(int start) {
LinkedList<Integer> result = new LinkedList<>();
boolean[] isVisited = new boolean[adjVertices.size()];
topologicalSortRecursive(start, isVisited, result);
return result;
}
private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedList<Integer> result) {
isVisited[current] = true;
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
topologicalSortRecursive(dest, isVisited, result);
}
result.addFirst(current);
}
✅ 关键点：使用 LinkedList 的 addFirst() 方法将节点按完成顺序插入头部，最终得到拓扑排序结果。
4. 总结
本文我们详细讲解了深度优先搜索（DFS）在 Java 中的实现，涵盖：
- 树结构的三种 DFS 遍历方式（前序、中序、后序）
- 图结构的 DFS 实现（递归和非递归）
- 拓扑排序的实现原理
这些算法是图论和树结构操作的基础，理解它们有助于解决更复杂的实际问题。
完整源码可以在 GitHub 上找到。