深度优先遍历（DFS）和广度优先遍历（BFS）

图的遍历：所谓遍历，即是对结点的访问。一个图有多个结点，如何遍历这些结点，有两种访问策略：

深度优先遍历(Depth First Search, 简称 DFS)
广度优先遍历(Breadth First Search 简称 BFS)

开发中广泛用于拓扑排序，寻路(走迷宫)，搜索引擎，爬虫等

一、深度优先遍历

1.1 主要思路

从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

1.2 实现过程

树是图的一种特例(连通无环的图就是树)，接下来我们来看看树用深度优先遍历该怎么遍历。
在这里插入图片描述

1、我们从根节点 1 开始遍历，它相邻的节点有 2，3，4，先遍历节点 2，再遍历 2 的子节点 5，然后再遍历 5 的子节点 9。
在这里插入图片描述

2、上图中一条路已经走到底了(9是叶子节点，再无可遍历的节点)，此时就从 9 回退到上一个节点 5，看下节点 5 是否还有除 9 以外的节点，没有继续回退到 2，2 也没有除 5 以外的节点，回退到 1，1 有除 2 以外的节点 3，所以从节点 3 开始进行深度优先遍历，如下：

3、同理从 10 开始往上回溯到 6, 6 没有除 10 以外的子节点，再往上回溯，发现 3 有除 6 以外的子点 7，所以此时会遍历 7。
在这里插入图片描述

3、从 7 往上回溯到 3， 1，发现 1 还有节点 4 未遍历，所以此时沿着 4， 8 进行遍历,这样就遍历完成了。

完整的节点的遍历顺序如下(节点上的的蓝色数字代表)：
在这里插入图片描述

树的前序遍历,实际上树的前序遍历、中序遍历、后序遍历，都属于深度优先遍历。

1.3 深度优先遍历的实现

递归和非递归两种表现形式，接下来我们以二叉树为例来看下如何分别用递归和非递归来实现深度优先遍历。

1.3.1 递归实现

递归实现比较简单，由于是前序遍历，所以我们依次遍历当前节点，左节点，右节点即可，对于左右节点来说，依次遍历它们的左右节点即可，依此不断递归下去，直到叶节点(递归终止条件)，代码如下：

    public class Solution { private static class Node { public int value; //节点值           public Node left;  //左节点            public Node right; //右节点public Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; } } public static void dfs(Node treeNode) { if (treeNode == null) { return; } // 遍历节点 process(treeNode) // 遍历左节点 dfs(treeNode.left); // 遍历右节点 dfs(treeNode.right); } }

递归的表达性很好，也很容易理解，不过如果层级过深，很容易导致栈溢出。所以我们重点看下非递归实现。

具体示例查看树一章案例中的Tree类中的 preOrder(Node localRoot) 方法

1.3.2 非递归实现

对二叉树来说，由于是先序遍历(先遍历当前节点，再遍历左节点，再遍历右节点)，我们可以通过栈来实现非递归

实现思路

压栈：对于每个节点来先遍历当前节点，然后把右节点压栈，再压左节点(这样弹栈的时候会先拿到左节点遍历，符合深度优先遍历要求)。

弹栈：拿到栈顶的节点，如果节点不为空，重复步骤，如果为空，结束遍历。

栈实现 DFS

在这里插入图片描述

栈实现的二叉树的深度优先遍历代码：

    /** * 使用栈来实现 dfs * @param root */ public static void dfsWithStack(Node root) { if (root == null) { return; } Stack<Node> stack = new Stack<>(); // 先把根节点压栈 stack.push(root); while (!stack.isEmpty()) { Node treeNode = stack.pop(); // 遍历节点 process(treeNode) // 先压右节点 if (treeNode.right != null) { stack.push(treeNode.right); } // 再压左节点 if (treeNode.left != null) { stack.push(treeNode.left); } } }

用栈实现深度优先遍历不用会象递归那样层级过深导致的栈溢出问题

具体示例查看树一章案例中的Tree类中的displayTree 方法

二、广度优先遍历

2.1主要思路

广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。

2.2 实现过程

树的广度优先遍历每个节点的值即为它们的遍历顺序。所以广度优先遍历也叫层序遍历，先遍历第一层(节点 1)，再遍历第二层(节点 2，3，4)，第三层(5，6，7，8)，第四层(9，10)。

队列实现BFS

在这里插入图片描述

2.3 代码：

    /** * 使用队列实现 bfs * @param root */ private static void bfs(Node root) { if (root == null) { return; } Queue<Node> stack = new LinkedList<>(); stack.add(root); while (!stack.isEmpty()) { Node node = stack.poll(); System.out.println("value = " + node.value); Node left = node.left; if (left != null) { stack.add(left); } Node right = node.right; if (right != null) { stack.add(right); } } }