本文分享自华为云社区《BFS和DFS算法初探》,作者: ayin。
本次分享两个常见的搜索算法
1.BFS 即广度优先搜索
2.DFS 即深度优先搜索
岛屿数量
给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
11110
11010
11000
00000
输出: 1
11000
11000
00100
00011
输出: 3
其实我们还是比较容易想到初步解法的,即从二维网络某点出发,寻找其四周相邻的陆地,直到所有包含的点都没有相邻的陆地为止,这里可以认为已经找到了一个岛屿,其余岛屿同理可以找到。这里的关键问题是遍历岛屿的顺序,其实不难看出有两种顺序
我们对第一种方法进行观察:
现在可以尝试写出实际的程序
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的动图和算法模板来加深印象
同样来观察第二中方法,我们发现
试着写出实际的程序
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的动图和模板算法(递归和栈)来加深印象
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://huaweicloud.blog.csdn.net/article/details/123174636
内容来源于网络,如有侵权,请联系作者删除!