Java数据结构与算法——深度优先搜索与广度优先搜索

一、定义

1、深度优先搜索（DFS）

深度优先搜索（DFS，Depth First Search），就是“一条路走到黑”。对每一个可能的分支路径深入到不能再深入为止，当访问某个节点到尽头时，返回上一个还没访问的节点继续进行深度优先搜索。

深度优先搜索常用栈（Stack）这种数据结构配合实现，利用 Stack 先进后出的特点。

2、广度优先搜索（BFS）

广度优先搜索（BFS，Breadth First Search），广度优先是连通图的一种遍历策略。它并不考虑结果的可能位置，而是彻底地搜索整张图，检查图中所有的节点，直到找到结果为止。

广度优先搜索常用队列（queue）这种数据结构配合实现，利用 queue 先进先出的特点。

二、案例

1、树的遍历

假设有一棵树，如下图：

（1）深度优先遍历

利用先进后出的 Stack 来实现，假设从左到右进行搜索遍历，遍历过程如下：

• 先将根节点 5 压入栈中，Stack（5）；
• 弹出栈顶元素 5，并将 5 的两个孩子 7、2 压入栈中，此时 2 在栈顶，Stack（2，7）（注意：这里进行从左到右的遍历顺序，所以先将右孩子压栈，左孩子就可以先弹出）；
• 弹出栈顶元素 2，并将 2 的两个孩子 3、1 压入栈中，此时 1 在栈顶，Stack（1，3，7）；
• 弹出栈顶元素 1，1 没有孩子，此时 3 在栈顶，Stack（3，7）；
• 弹出栈顶元素 3，并将 3 的孩子 4 压入栈中，此时 4 在栈顶，Stack（4，7）；
• 弹出栈顶元素 4，4 没有孩子，此时 7 在栈顶，Stack（7）；
• 弹出栈顶元素 7，并将 7 的孩子 6 压入栈中，此时 6 在栈顶，Stack（6）；
• 弹出栈顶元素 6，6 没有孩子，此时 Stack 为空，遍历完毕。

深度优先遍历的结果为：5，2，1，3，4，7，6。

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public void depthFirst(TreeNode root){
    if(root == null)
        return;
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.add(root);
    while(!stack.isEmpty){
        TreeNode node = stack.pop();
        System.out.print(node.val + ", ");
        if(node.right != null)
            stack.add(node.right);
        if(node.left != null)
            stack.add(node.left);    
    }
}

（2）广度优先遍历

广度优先遍历即为树的层序遍历，利用先进先出的 queue 来实现。过程如下：

• 先将根节点 5 入队，queue（5）；
• 队头 5 出队，并将 5 的两个孩子 2、7 入队（先左后右），此时 2 在队头，7 在队尾，queue（2，7）；
• 队头 2 出队，并将 2 的两个孩子 1、3 入队，此时 7 在队头，3 在队尾，queue（7，1，3）；
• 队头 7 出队，并将 7 的孩子 6 入队，此时 1 在队头，6 在队尾，queue（1，3，6）；
• 队头 1 出队，1 没有孩子，此时 3 在队头，6 在队尾，queue（3，6）；
• 队头 3 出队，并将 3 的孩子 4 入队，此时 6 在队头，4 在队尾，queue（6，4）；
• 队头 6 出队，6 没有孩子，queue（4）；
• 队头 4 出队，队列为空，遍历完毕。

广度优先遍历（层序遍历）的结果为：5，2，7，1，3，6，4。

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public void breadthFirst(TreeNode root){
    if(root == null)
        return;
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty){
        TreeNode node = queue.poll();
        System.out.print(node.val + ", ");
        if(node.left != null)
            queue.add(node.left); 
        if(node.right != null)
            queue.add(node.right);
    }
}

2、二叉树的最大深度

leetcode刷题（10）——104.二叉树的最大深度