Depth First Search in Java

àì夳堔傛蜴生んèń 2024-04-17 21:54 46阅读 0赞

# 1. 概述 #

在本教程中，我们将探讨Java中的深度优先搜索

深度优先搜索（DFS）是一个应用于树、图等数据结构的遍历算法。在移动到下一个分支之前，深度优先搜索会  
深度为优先原则去探索新的分支。

在接下来的部分中，我们将首先了解树的实现，然后是图。

要了解如何在Java中实现这些结构，请查看我们以前的关于 [二叉树 Binary Tree][Binary Tree] 和 [图 Graph][Graph] 的教程。

# 2. 树的深度优先搜索 #

使用 DFS 遍历树有三种不同的顺序：

*  先序遍历
 *  中序遍历
 *  后序遍历

## 2.1 先序遍历 ##

在先序遍历中，先遍历其根节点，依次是左子树和右子树。

使用递归简单地实现先序遍历：

*  访问当前节点
 *  遍历左子树
 *  遍历右子树

public void traversePreOrder(Node node) {
        
        if (node != null) {
        
            visit(node.value);
            traversePreOrder(node.left);
            traversePreOrder(node.right);
        }
    }

使用非递归方式实现先序遍历：

*  将根节点入栈
 *  当栈不为空
    
     *  将当前节点（栈顶元素）弹栈
     *  访问当前节点
     *  依次将当前节点右子节点、左子节点入栈

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 中序遍历 ##

对于中序遍历，先访问其左子树，然后根节点，最后访问右子树。

二叉搜索树的中序遍历意味着按值的递增顺序遍历节点。

使用递归实现中序遍历：

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>();
        Node current = root;
        stack.push(root);
        while(! stack.isEmpty()) {
        
            while(current.left != null) {
        
                current = current.left;                
                stack.push(current);                
            }
            current = stack.pop();
            visit(current.value);
            if(current.right != null) {
        
                current = current.right;                
                stack.push(current);
            }
        }
    }

## 2.3 后序遍历 ##

最后，在后序遍历中，在访问根节点之前，依次先访问左子节点、右子节点。

参考前边，递归实现后序遍历：

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>();
        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. 图的深度优先搜索 #

图和树之间的主要区别在于图可能包含循环。

因此，为了避免循环搜索，我们将在访问每个节点时对其进行标记。

接下来将会展示图DFS的递归、非递归实现。

## 3.1 图的DFS递归实现 ##

首先，让我们从递归开始：

*  从一个任意的节点开始
 *  标记当前节点为已访问
 *  访问当前节点
 *  遍历未访问的相邻节点

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 图的DFS非递归实现 ##

也可以在不使用递归的情况下实现图的DFS。我们也需要使用一个栈进行实现：

*  将从一个任意的节点开始
 *  将节点压栈
 *  当栈不为空
    
     *  标记当前节点为已访问
     *  访问当前节点
     *  将未访问的相邻顶点压栈

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();
            isVisited[current] = true;
            visit(current);
            for (int dest : adjVertices.get(current)) {
        
                if (!isVisited[dest])
                    stack.push(dest);
            }
        }
    }

## 3.4 拓扑排序 ##

图的深度优先搜索有很多应用。拓扑排序是深度优先搜索最著名的应用之一。

有向图的拓扑排序是其顶点的线性排序，因此对于每个边，源节点都位于目标之前。

要进行拓扑排序，需要对刚刚实现的DFS进行简单的改造：

*  我们需要将访问的顶点保持在堆栈中，因为拓扑排序是以相反的顺序访问的顶点
 *  只有在遍历所有相邻节点之后，才会将访问的节点推送到堆栈中。

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. 结论 #

在本文中，我们讨论了树和图的深度优先搜索。

完整代码见 [GitHub][] 。

> 原文：https://www.baeldung.com/java-depth-first-search  
> 作者：baeldung  
> 译者：陈苓洪

[Binary Tree]: https://www.baeldung.com/java-binary-tree
[Graph]: https://www.baeldung.com/java-graphs
[GitHub]: https://github.com/eugenp/tutorials/tree/master/data-structures