国内最便宜机票网站建设,手机小游戏网站,wordpress微信登录页面模板,菠菜网站怎么做排名深度优先遍历(Depth First Search#xff0c;简称DFS) 与广度优先遍历(Breath First Search#xff0c;简称BFS)是图论中两种非常重要的算法#xff0c;生产上广泛用于拓扑排序#xff0c;寻路(走迷宫)#xff0c;搜索引擎#xff0c;爬虫等。
一、深度优先遍历 深度优先…深度优先遍历(Depth First Search简称DFS) 与广度优先遍历(Breath First Search简称BFS)是图论中两种非常重要的算法生产上广泛用于拓扑排序寻路(走迷宫)搜索引擎爬虫等。
一、深度优先遍历 深度优先遍历的思路是从图的一个未访问的顶点V开始沿着一条路一直走到底然后从这条路尽头的节点回退到上一个节点再从另一条路开始走到底不断递归重复此过程…直到所有的顶点都遍历完成。它的特点说通俗了就是不撞南墙不回头走完了一条路再换一条路继续走。 树是图的一种特例 联通无环的图就是树接下来我们来看树用深度优先遍历该怎么遍历。 1、深度优先遍历过程 1、我们从根节点1开始深度优先遍历它相邻的节点有2、3、4依先遍历节点2再遍历2的右边节点5再遍历9至此便无可遍历的节点。
2、上图中一条路径已经遍历到底此时从叶子节点9回退到上一节点5看下节点 5 是否还有除 9 以外的节点没有继续回退到 22 也没有除 5 以外的节点回退到 11 有除 2 以外的节点 3所以从节点 3 开始进行深度优先遍历如下 3、同理从 10 开始往上回溯到 6, 6 没有除 10 以外的子节点再往上回溯发现3有除 6 以外的子节点 7所以此时会遍历 7。 4、从 7 往上回溯到 3 1发现 1 还有节点 4 未遍历所以此时沿着 4 8 进行遍历这样就完成了整个遍历过程。 完整的节点的遍历顺序如下(节点上的的蓝色数字代表) 相信大家看到以上的遍历不难发现这就是树的前序遍历实际上不管是前序遍历还是中序遍历亦或是后序遍历都属于深度优先遍历。
那么深度优先遍历该怎么实现呢有递归和非递归两种表现形式接下来我们以二叉树为例来看下如何分别用递归和非递归来实现深度优先遍历。 2、深度优先遍历实现 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); // 遍历右节点}
} 递归的表达性很好也很容易理解不过如果层级过深很容易导致栈溢出。所以我们重点看下非递归实现。 2、非递归 仔细观察深度优先遍历的特点对二叉树来说由于是先序遍历(先遍历当前节点再遍历左节点再遍历右节点)所以我们有如下思路
对于每个节点来说先遍历当前节点然后把右节点压栈再压左节点(这样弹栈的时候会先拿到左节点遍历符合深度优先遍历要求)。 弹栈拿到栈顶的节点如果节点不为空重复步骤 1 如果为空结束遍历。 我们以以下二叉树为例来看下如何用栈来实现 DFS。
使用栈来将要遍历的节点压栈然后出栈后检查此节点是否还有未遍历的节点有的话压栈没有的话不断回溯(出栈)有了思路不难写出如下用栈实现的二叉树的深度优先遍历代码
/** * 使用栈来实现 dfs * param root */
public static void dfsWithStack(Node root) { if (root null) { return; } StackNode 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); } }
}二、深度优先遍历 广度优先遍历指的是从图的一个未遍历的节点出发先遍历这个节点的相邻节点再依次遍历每个相邻节点的相邻节点。
上面所述树的广度优先遍历动图如下每个节点的值即为它们的遍历顺序。所以广度优先遍历也叫层序遍历先遍历第一层(节点 1)再遍历第二层(节点 234)第三层(5678)第四层(910)。
深度优先遍历用的是栈而广度优先遍历要用队列来实现我们以下图二叉树为例来看看如何用队列来实现广度优先遍历。 代码实现如下
/** * 使用队列实现 bfs * param root */
private static void bfs(Node root) { if (root null) { return; } QueueNode 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); } }
} 若想通过实战来进一步理解DFS,BFS可以看LeetCode如下题目这是一道典型的DFS,BFS题目。 leetcode 104111: 给定一个二叉树找出其最大/最小深度。
