算法学习（18）—深度优先遍历DFS

1、什么是优先遍历

①也就是我们说的深度搜索算法

②实现方式：利用栈和递归来实现

③思路：通过栈来实现的，找到一个起点A，并将A相邻的点放入栈中，将栈顶元素B取出,并将B相邻且没有访问过的点放入栈中，不断重复这个操作，直至栈清空，这时候，依次访问的顶点就是遍历的顺序。

④适用场景：于快速发现底部节点

连通图的深度优先遍历类似于树的前序遍历

2、优先遍历的原理

下面结合一个图(graph)的实例，说明DFS的工作过程和原理：

（1）将起始节点1放入栈stack中，标记为已遍历。

（2）从stack中访问栈顶的节点1，找出与节点1邻接的节点，有2,9两个节点，我们可以选择其中任何一个，选择规则可以人为设定，这里假设按照节点数字顺序由小到大选择，选中的是2，标记为已遍历，然后放入stack中。

（3）从stack中取出栈顶的节点2，找出与节点2邻接的节点，有1,3,5三个节点，节点1已遍历过，排除；3,5中按照预定的规则选中的是3，标记为已遍历，然后放入stack中。

（4）从stack中取出栈顶的节点3，找出与节点3邻接的节点，有2,4两个节点，节点2已遍历过，排除；选中的是节点4，标记为已遍历，然后放入stack中。

（5）从stack中取出栈顶的节点4，找出与节点4邻接的节点，有3,5,6三个节点，节点3已遍历过，排除；选中的是节点5，标记为已遍历，然后放入stack中。

（6）从stack中取出栈顶的节点5，找出与节点5邻接的节点，有2,4两个节点，节点2,4都已遍历过，因此节点5没有尚未遍历的邻接点，则将此点从stack中弹出。

（7）当前stack栈顶的节点是4，找出与节点4邻接的节点，有3,5,6三个节点，节点3,5都已遍历过，排除；选中的是节点6，标记为已遍历，然后放入stack中。

（8）当前stack栈顶的节点是6，找出与节点6邻接的节点，有4,7,8三个节点，4已遍历，按照规则选中的是7，标记为已遍历，然后放入stack中。

（9）当前stack栈顶的节点是7，找出与节点7邻接的节点，只有节点6，已遍历过，因此没有尚未遍历的邻接点，将节点7从stack中弹出。

（10）当前stack栈顶的节点是6，找出与节点6邻接的节点，有节点7,8，7已遍历过，因此将节点8放入stack中。

（11）当前stack栈顶的节点是8，找出与节点8邻接的节点，有节点1,6,9，1,6已遍历过，因此将节点9放入stack中。

（12）当前stack栈顶的节点是9，没有尚未遍历的邻接点，将节点9弹出，依次类推，栈中剩余节点8,6,4,3,2,1都没有尚未遍历的邻接点，都将弹出，最后栈为空。

3、优先遍历的实现

存储图的两种方式：邻接表和邻接矩阵

//二叉树的深度优先遍历
public class DFS {

    public static void main(String[] args) {
        TreeNode rootNode = buildTree();
        depthOrderTraversalWithOutRecusive(rootNode);
    }

    public static void depthOrderTraversalWithRecusive(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print("->" + node.getVal());
        depthOrderTraversalWithRecusive(node.getLeft());
        depthOrderTraversalWithRecusive(node.getRight());
    }


    public static void depthOrderTraversalWithOutRecusive(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack();
        stack.push(node);
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            System.out.print("->" + current.getVal());
            if (current.getRight() != null) {
                stack.push(current.getRight());
            }
            if (current.getLeft() != null) {
                stack.push(current.getLeft());
            }
        }
    }

    public static TreeNode buildTree() {
        TreeNode head = new TreeNode(1);
        TreeNode second = new TreeNode(2);
        TreeNode three = new TreeNode(3);
        TreeNode four = new TreeNode(4);
        TreeNode five = new TreeNode(5);
        TreeNode six = new TreeNode(6);
        TreeNode seven = new TreeNode(7);
        head.right = three;
        head.left = second;
        second.right = five;
        second.left = four;
        three.right = seven;
        three.left = six;
        return head;
    }
}