1. Overview
1.概述
In this tutorial, we’ll explore the Depth-first search in Java.
在本教程中，我们将探讨Java中的深度优先搜索。
Depth-first search (DFS) is a traversal algorithm used for both Tree and Graph data structures. The depth-first search goes deep in each branch before moving to explore another branch.
深度优先搜索（DFS）是一种用于Tree和Graph数据结构的遍历算法。深度优先搜索会深入到每个分支，然后再去探索另一个分支。
In the next sections, we’ll first have a look at the implementation for a Tree and then a Graph.
在接下来的章节中，我们将首先看一下树和图的实现。
To see how to implement these structures in Java, have a look at our previous tutorials on Binary Tree and Graph.
要了解如何在Java中实现这些结构，请看我们以前的二叉树和图形教程。
2. Tree Depth-first Search
2.树形深度优先搜索
There are three different orders for traversing a tree using DFS:
使用DFS遍历一棵树，有三种不同的顺序。
- Preorder Traversal
- Inorder Traversal
- Postorder Traversal
2.1. Preorder Traversal
2.1 前序遍历
In preorder traversal, we traverse the root first, then the left and right subtrees.
在前序遍历中，我们先遍历根，然后是左、右子树。。
We can simply implement preorder traversal using recursion:
我们可以简单地使用递归实现预排序遍历。
- Visit current node
- Traverse left subtree
- Traverse right subtree
public void traversePreOrder(Node node) {
if (node != null) {
visit(node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}We can also implement preorder traversal without recursion.
我们也可以实现没有递归的前序遍历。
To implement an iterative preorder traversal, we’ll need a Stack, and we’ll go through these steps:
为了实现迭代预排序遍历，我们需要一个Stack，我们将通过这些步骤。
- Push root in our stack
- While stack is not empty
- Pop current node
- Visit current node
- Push right child, then left child to stack
public void traversePreOrderWithoutRecursion() {
Stack<Node> stack = new Stack<Node>();
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
2.2 顺序遍历
For inorder traversal, we traverse the left subtree first, then the root, then finally the right subtree.
对于无序遍历，我们先遍历左子树，然后是根，最后是右子树。
Inorder traversal for a binary search tree means traversing the nodes in increasing order of their values.
二进制搜索树的无序遍历是指按照节点价值的增加顺序遍历节点。
We can simply implement inorder traversal using recursion:
我们可以简单地使用递归来实现无序遍历：。
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
visit(node.value);
traverseInOrder(node.right);
}
}We can also implement inorder traversal without recursion, too:
我们也可以实现无递归的无序遍历，。
- Initialize current node with root
- While current is not null or stack is not empty
- Keep pushing left child onto stack, till we reach current node’s left-most child
- Pop and visit the left-most node from stack
- Set current to the right child of the popped node
public void traverseInOrderWithoutRecursion() {
Stack 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
2.3 后置订单遍历
Finally, in postorder traversal, we traverse the left and right subtree before we traverse the root.
最后，在后序遍历中，我们在遍历根部之前遍历左、右子树。
We can follow our previous recursive solution:
我们可以按照我们之前的递归解决方案。
public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
visit(node.value);
}
}Or, we can also implement postorder traversal without recursion:
或者，我们也可以实现无递归的后序遍历。
- Push root node in stack
- While stack is not empty
- Check if we already traversed left and right subtree
- If not then push right child and left child onto stack
public void traversePostOrderWithoutRecursion() {
Stack<Node> stack = new Stack<Node>();
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);
}
}
}
}3. Graph Depth-first Search
3.图的深度优先搜索
The main difference between graphs and trees is that graphs may contain cycles.
图和树的主要区别在于，图可能包含循环。
So to avoid searching in cycles, we will mark each node when we visit it.
所以为了避免循环搜索，我们将在访问每个节点时对其进行标记。
We’ll see two implementations for graph DFS, with recursion, and without recursion.
我们将看到图DFS的两种实现方式，有递归和无递归。
3.1. Graph DFS with Recursion
3.1.带递归的图DFS
First, let’s start simple with recursion:
首先，让我们从简单的递归开始。
- We’ll start from a given node
- Mark current node as visited
- Visit current node
- Traverse unvisited adjacent vertices
public void dfs(int start) {
boolean[] isVisited = new boolean[adjVertices.size()];
dfsRecursive(start, isVisited);
}
private void dfsRecursive(int current, boolean[] isVisited) {
isVisited[current] = true;
visit(current);
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
dfsRecursive(dest, isVisited);
}
}3.2. Graph DFS Without Recursion
3.2.没有递归的图DFS
We can also implement graph DFS without recursion. We’ll simply use a Stack:
我们也可以实现没有递归的图DFS。我们将简单地使用一个Stack。
- We’ll start from a given node
- Push start node into stack
- While Stack not empty
- Mark current node as visited
- Visit current node
- Push unvisited adjacent vertices
public void dfsWithoutRecursion(int start) {
Stack<Integer> stack = new Stack<Integer>();
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);
}
}
}3.4. Topological Sort
3.4.拓扑学排序
There are a lot of applications for graph depth-first search. One of the famous applications for DFS is Topological Sort.
图深度优先搜索有很多的应用。DFS的一个著名应用是拓扑排序。
Topological Sort for a directed graph is a linear ordering of its vertices so that for every edge the source node comes before the destination.
有向图的拓扑排序是指对其顶点进行线性排序，使每条边的源节点都在目的地之前。
To get topologically sorted, we’ll need a simple addition to the DFS we just implemented:
为了获得拓扑排序，我们需要对刚刚实现的DFS进行简单的补充。
- We need to keep the visited vertices in a stack because the topological sort is the visited vertices in a reversed order
- We push the visited node to the stack only after traversing all its neighbors
public List<Integer> topologicalSort(int start) {
LinkedList<Integer> result = new LinkedList<Integer>();
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);
}4. Conclusion
4.结论
In this article, we discussed the depth-first search for both the Tree and Graph data structures.
在这篇文章中，我们讨论了树和图数据结构的深度优先搜索。
The full source code is available on GitHub.
完整的源代码可在GitHub上获得。