广度优先搜索和深度优先搜索都可以用于遍历一棵树（广度优先搜索和深度优先搜索例题）



        DFS在定义上其实就是一个二叉树的先序遍历，从根节点开始不断遍历当前节点的左子树、右子树，当碰到空子树的时候及时返回，并不断递归的过程。

        这里附上二叉树的DFS遍历结构：

        可以看到，二叉树的 DFS 有两个要素：「访问相邻结点」和「判断 base case」。

        那么我们从二叉树的思路推广到网格结构，网格中的一个点有几个相邻节点？答案是4个。一个格子可以有上下左右四个方向搜索（这里先不考虑边界情况），这样我们就轻松的解决了第一个要素，访问相邻节点只需要访问当前各自的上下左右四个格子就可以了。换句话说，网格结构是一个四叉树。

        现在要处理的是判断base case，一个节点的base case其实就是不需要再遍历下去后者在遍历会出现错误的情况。显而易见的如果我们遍历到网格中的边界格子时会出现再向外遍历就越界的情况，这就需要我们在遍历的过程中加一步判断，判断要遍历的下一个格子是否还在网格范围内。

        这样，我们就得到了一个岛屿问题、乃至各种网格问题的通用 DFS 遍历方法。所有这系列的例题，其实都只需要在 DFS 遍历框架上稍加修改而已。

        这里拿举例，题解如下。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rgzn-sdxx/48688.html