Dayup
目录

深度优先搜索

Dayup 约 9 分钟 技术 算法
目录

一、概述

深度优先搜索是一种遍历算法，可以用于遍历树或者图。深度优先搜索在遍历另一个分支之前，一定会遍历完当前分支。
接下来，我们来看看这种算法在树和图的遍历中是怎么实现的。

二、树结构中的深度优先搜索

对于树结构而言，有三种不同的方式遍历树，分别是：

  • 前序遍历
  • 中序遍历
  • 后序遍历

（一）前序遍历

  1. 递归法
    对于前序遍历，我们首先遍历树的根节点，然后是左子树，最后是右子树。
    我们可以简单地使用递归实现前序遍历，代码及步骤如下：
public void traversePreOrder(Node node) {
    if (node != null) {
        visit(node.value);                          //1. 访问当前节点
        traversePreOrder(node.left);                //2. 遍历左子树
        traversePreOrder(node.right);               //3. 遍历右子树
    }
}
  1. 迭代法
    我们也可以不使用递归实现前序遍历。
    为了实现迭代前序遍历，我们需要一个 Stack，具体代码及实现步骤如下：
public void traversePreOrderWithoutRecursion() {
    Stack<Node> stack = new Stack<Node>();
    Node current = root;
    stack.push(root);                               //1. push根节点到栈中
    while(!stack.isEmpty()) {                       //2. 当栈不为空时
        current = stack.pop();                          //2-1 pop并访问当前节点
        visit(current.value);
        
        if(current.right != null) {                     //2-2 push右节点
            stack.push(current.right);
        }

        if(current.left != null) {                      //2-3 push左节点
            stack.push(current.left);
        }
    }        
}

（二）中序遍历

对于中序遍历，我们首先遍历左子树，然后是根节点，最后是右子树。

  1. 递归法
public void traverseInOrder(Node node) {
    if (node != null) {
        traverseInOrder(node.left);                 //1. 遍历左子树
        visit(node.value);                          //2. 访问当前节点
        traverseInOrder(node.right);                //3. 遍历右子树
    }
}
  1. 迭代法
public void traverseInOrderWithoutRecursion() {
    Stack<Node> stack = new Stack<Node>();
    Node current = root;
    stack.push(root);                               //1. push根节点到栈中
    while(! stack.isEmpty()) {                      //2. 当栈不为空时
        while(current.left != null) {                    //2-1 持续push左节点，直到到达当前节点的最左孩子节点
            current = current.left;                
            stack.push(current);
        }

        current = stack.pop();                          //2-3 pop并访问当前节点
        visit(current.value);

        if(current.right != null) {                     //2-4 push右节点
            current = current.right;                
            stack.push(current);
        }
    }
}

（三）后序遍历

对于后序遍历，我们首先遍历左子树，然后是右子树，最后是根节点。

  1. 递归法
public void traversePostOrder(Node node) {
    if (node != null) {
        traversePostOrder(node.left);                 //1. 遍历左子树
        traversePostOrder(node.right);                //2. 遍历右子树
        visit(node.value);                            //3. 访问当前节点
    }
}
  1. 迭代法
public void traversePostOrderWithoutRecursion() {
    Stack<Node> stack = new Stack<Node>();
    Node prev = root;
    Node current = root;
    stack.push(root);                               //1. push根节点到栈中

    while (!stack.isEmpty()) {                      //2. 当栈不为空时
        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) {             //2-1 检查我们是否已经遍历了左右子树
            current = stack.pop();
            visit(current.value);
            prev = current;
        } else {                                        //2-2 如果没有，则将右孩子和左孩子推入堆栈
            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }
        }
    }   
}

三、图结构中的深度优先搜索

图和树的主要区别是，图包含环。为了避免在环内搜索，需要在遍历节点后对节点进行标记。

  1. 递归法
public void dfs(int start) {
    boolean[] isVisited = new boolean[adjVertices.size()];
    dfsRecursive(start, isVisited);             //1 从一个给定的节点开始
}

private void dfsRecursive(int current, boolean[] isVisited) {   //2 进入递归函数
    isVisited[current] = true;                                      //2-1 标记当前节点为已遍历
    visit(current);                                                 //2-2 获取节点值
    for (int dest : adjVertices.get(current)) {                     //2-3 遍历未遍历的相邻节点
        if (!isVisited[dest])
            dfsRecursive(dest, isVisited);
    }
}
  1. 迭代法
public void dfsWithoutRecursion(int start) {
    Stack<Integer> stack = new Stack<Integer>();
    boolean[] isVisited = new boolean[adjVertices.size()];
    stack.push(start);                          //1. 从一个给定的节点开始,push “start” 节点进栈
    while (!stack.isEmpty()) {                  //2. 当栈不为空时
        int current = stack.pop();
        isVisited[current] = true;                  //2-1 标记当前节点为已遍历
        visit(current);                             //2-2 获取节点值
        for (int dest : adjVertices.get(current)) { //2-3 遍历未遍历的相邻节点
            if (!isVisited[dest])
                stack.push(dest);
        }
    }
}
  1. 拓扑排序
    图深度优先搜索有很多应用。 DFS 的著名应用之一是拓扑排序。
    有向图的拓扑排序是其节点的线性排序，因此对于每条边，源节点都在目标节点之前。
    为了进行拓扑排序，我们需要对刚刚实现的 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);
}

四、小结

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

参考：

  1. https://www.baeldung.com/java-depth-first-search —by baeldung
← 返回技术