摘要：本文为大家分享两个常见的搜索算法：BFS 和 DFS。
本文分享自华为云社区《BFS和DFS算法初探》，作者： ayin。
本次分享两个常见的搜索算法：
1.BFS 即广度优先搜索
2.DFS 即深度优先搜索
岛屿数量
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输出: 1
示例 2:
输出: 3
其实我们还是比较容易想到初步解法的，即从二维网络某点出发，寻找其四周相邻的陆地，直到所有包含的点都没有相邻的陆地为止，这里可以认为已经找到了一个岛屿，其余岛屿同理可以找到。这里的关键问题是遍历岛屿的顺序，其实不难看出有两种顺序
a.
优先寻找某 a 节点的所有相邻位置
然后拿出一个相邻位置比如说 b 寻找其所有相邻位置
拿出 a 节点下一个相邻位置重复第 2 步直到 a 节点的相邻位置都执行过该操作
拿出 b，重复 1，2，3 步
b.
优先寻找 a 节点的相邻位置比如说 b
寻找 b 的相邻位置 c
直到没有相邻位置后再返回到 a 的下一个相邻位置，重复 1，2 步
§ 方案一
我们对第一种方法进行观察：
越是接近根结点的结点将越早地遍历
思考用什么存储结构来存放我们找到的位置：我们把 root 的相邻位置存储到 x 结构中，然后取出 x 的某个相邻位置 a，寻找其相邻位置继续存放到 x 中，再取出 x 中与 root 相邻的下个位置 b 继续寻找其相邻位置放入 x 中。这里我们发现我们存储 x 的顺序与我们处理 x 得到其他数据的顺序一致：先进先出（FIFO），不难得出我们可以采用队列来存储
需要一种方法避免对已经找到的位置重复访问
现在可以尝试写出实际的程序
public int numIslands(char[][] grid) { if (grid.length==0){ return 0; } Queue<Point> queue = new LinkedList<>(); int count =0; for(int y=0;y<grid.length;y++){ for(int x=0;x<grid[0].length;x++){ // 核心部分 if(grid[y][x]=='1'){ queue.offer(new Point(x,y)); while (queue.size() != 0) { Point nowPoint = queue.peek(); List<Point> pointList = getNearPoints(nowPoint, grid); for (Point point : pointList) { queue.offer(point); // 标记已经访问的位置 grid[point.y][point.x] = '2'; System.out.println(point.y * grid[0].length + point.x); } queue.poll(); } count++; } // 核心部分 } }
复制代码
通过这个实例我们可以进一步抽象为图论中的一种算法–BFS 可以参考 leetcode 的动图和算法模板来加深印象
§ 方案二
同样来观察第二中方法，我们发现
优先走完一条路径直到结束
我们需要在某一路径结束后，回溯到初始位置，即存储节点位置的顺序和处理的顺序相反，即现进后出（FILO）。这里我们可以用递归或者栈来处理。
试着写出实际的程序
1.递归
public int numIslands(char[][] grid) { int len = 0; Set <Integer> visited = new HashSet<>(); for (int y = 0; y < grid.length; y++) { for (int x = 0; x < grid[0].length; x++) { Integer node = y * grid[0].length + x; if (!visited.contains(node)&&grid[y][x] == '1') { visited.add(node); DFS3(node, visited, grid); len++; } } } return len; } boolean DFS(Integer cur, Set<Integer> visited,char [][]grid) { for (Integer next : getNearNodes(cur,grid[0].length,grid.length,grid)) { if (!visited.contains(next)) { visited.add(next); System.out.println(next); DFS(next,visited,grid); } } return true; }
复制代码
2.栈
boolean DFS3(Integer cur, Set<Integer> visited,char [][]grid){ Stack<Integer> nodeStack = new Stack<>(); nodeStack.push(cur); while(!nodeStack.empty()){ Integer node = nodeStack.peek(); boolean hasNearNode = false; for(Integer next:getNearNodes(node,grid[0].length,grid.length,grid)){ if(!visited.contains(next)){ visited.add(next); nodeStack.push(next); hasNearNode = true; } } // 如果当前节点没有邻居则去除栈顶节点 if(!hasNearNode){ nodeStack.pop(); } } return true; }
复制代码
通过这个实例我们可以进一步抽象为图论中的一种算法–DFS
参考 leetcode 的动图和模板算法（递归和栈）来加深印象
点击关注，第一时间了解华为云新鲜技术~
评论