广度优先搜索和深度优先搜索

二叉树.jpg

广度优先搜索

介绍：又称宽度优先搜索，英文缩写为BFS。属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。其核心就在于使用队列Queue来做一个while循环，在循环内除了对当前节点的处理之外，还需要将当前节点的孩子节点放入队列的尾部。

应用：
1、在求解最短路径或者最短步数上有很多的应用。
2、几度好友
（注：Queue/Linkedlist/HashSet）

要点：
1、先进先出队列（Queue）
2、遍历所有节点（while）
3、每个节点只能访问一次（HashSet）

    //广度优先搜索
    public void doBFS(TreeNode root) {
        if (root == null) {
            return;
        }
        //初始化队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //把根节点加入队列
        queue.add(root);
        //记录遍历过的节点
        HashSet<TreeNode> visited = new HashSet<TreeNode>();
        //开始遍历队列
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            //当前节点没有遍历过
            if (!visited.contains(current)) {
                visited.add(current);
                //只要当前节点的左右节点不为空
                if (current.left != null) {
                    queue.add(current.left);
                }
                if (current.right != null) {
                    queue.add(current.right);
                }
            }

        }

    }

深度优先搜索

介绍：深度优先搜索属于图算法的一种，英文缩写为DFS。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。总的来说只要搜索集合相对固定，并且使用到递归的算法都可以算是深度优先。

递归简单的理解就是自己调用自己（所谓递归，就是包含递推和回归两个自然过程，一方面要由外到里地深入，一方面又要由里到外地回到原点）

应用：
1、迷宫
2、回溯相关问题

要点：
1、搜索集合相对固定
2、使用到栈/递归
3、每个节点只能访问一次

    /**
     * 栈
     */
    public void doDFS(TreeNode root) {
        if (root == null) {
            return;
        }
        HashSet<TreeNode> visited = new HashSet<TreeNode>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tree = stack.pop();
            if (!visited.contains(current)) {
                visited.add(current);
                //先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。
                if (tree.right != null)
                    stack.push(tree.right);
                if (tree.left != null)
                    stack.push(tree.left);
            }
        }
    }

    /**
     * 递归实现
     */
    public void doDFS(TreeNode root) {
        depthTraversal(root);
    }

    private void depthTraversal(TreeNode tn) {
        if (tn != null) {
            depthTraversal(tn.left);
            depthTraversal(tn.right);
        }
    }

对比

1、如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。
如果扩展是首先扩展新产生的状态，则叫深度优先搜索。
深度优先搜索：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。
广度优先搜索：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

2、 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。

3、通常 深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。 　
广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。

例题:
在手机上按几个数字键，输出对应可能产生的所有可能的字母的集合。

手机键盘