图论岛屿问题DFS+BFS

这篇具有很好参考价值的文章主要介绍了图论岛屿问题DFS+BFS。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode 200 岛屿问题

class Solution {
    //定义对应的方向
    boolean [][] visited;
    int dir[][]={
            {0,1},{1,0},{-1,0},{0,-1}
    };

    public int numIslands(char[][] grid) {
       //对应的二维数组
    int count=0;
    visited=new boolean[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (visited[i][j] == false && grid[i][j]=='1') {
                    count++;
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }

    public  void dfs(char[][]grid,int x,int y)
    {
        if (visited[x][y]==true||grid[x][y]=='0'){
            return;
        }
        visited[x][y]=true;

        for (int i = 0; i <4; i++) {
            int nextX=x+dir[i][0];
            int nextY=y+dir[i][1];
            if (nextY<0||nextX<0||nextX>=grid.length||nextY>=grid[0].length){
                continue;
            }
            dfs(grid,nextX,nextY);
        }

    }
}

BFS代码文章来源地址https://www.toymoban.com/news/detail-700653.html

class  Solution{
    boolean[][] visited;
    int move[][]={
            {0,1},{0,-1},{1,0},{-1,0}};
    public int numIslands(char[][] grid) {
        int res=0;
        visited=new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (!visited[i][j]&&grid[i][j]=='1'){
                    bfs(grid,i,j);
                    res++;
                }
            }
        }
        return  res;
    }
    public  void bfs(char [][] grid,int x,int y){
        Deque<int[]> queue=new ArrayDeque<>(); //创建一个队列
        queue.offer(new int[]{x,y});
        visited[x][y]=true;
        while (!queue.isEmpty()){
            int []cur=queue.poll();
            int m=cur[0];
            int n=cur[1];
            for (int i=0;i<4;i++){
                int nextx=m+move[i][0];
                int nexty=n+move[i][1];
                if (nextx<0||nextx==grid.length||nexty<0||nexty==grid[0].length){
                  continue;
                }
                if (!visited[nextx][nexty]&&grid[nextx][nexty]=='1'){
                    queue.offer(new int[]{nextx,nexty});
                    visited[nextx][nexty]=true;
                }
            }
        }
    }

到了这里,关于图论岛屿问题DFS+BFS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • U4_1:图论之DFS/BFS/TS/Scc

    由点(vertices)和边(edges)组成 G = ( V , E ) G=(V,E) G = ( V , E ) , ∣ V ∣ = n |V|=n ∣ V ∣ = n , ∣ E ∣ = m |E|=m ∣ E ∣ = m (这里默认有向图,无向图用 G G G = = = { V V V , E E E }表示 顶点的度是关联在其上的边的数量。满足 ∑ d e g r e e ( v ) = 2 ∣ E ∣ sum degree(v)=2|E| ∑ d e g ree ( v ) = 2∣

    2024年02月05日
    浏览(38)
  • 【寸铁的刷题笔记】树、回溯、图论、bfs、dfs(四)

    大家好 我是寸铁👊 金三银四 , 图论基础 、 回溯 结合 bfs 、 dfs 是必考的知识点✨ 快跟着寸铁刷起来!面试顺利上岸👋 喜欢的小伙伴可以点点关注 💝 🌞详见如下专栏🌞 🍀🍀🍀 寸铁的刷题笔记 🍀🍀🍀 考点 dfs、回溯 代码 考点 dfs、回溯 代码 考点 bfs、宽度搜索、哈

    2024年03月11日
    浏览(53)
  • 【算法基础:搜索与图论】3.2 树与图的dfs和bfs

    要学会建树、建图的通用方法。 dfs 和 bfs 的代码框架。 https://www.acwing.com/problem/content/848/ 在 dfs 的过程中,统计各个节点作为断点时的连通块最大值。 https://www.acwing.com/problem/content/849/ 看到最短距离就可以想到使用宽搜。 注意! :题目中说明了 a 和 b 表示存在一条从 a 走到

    2024年02月16日
    浏览(39)
  • 【算法导论】图论(图的基本概念,图上的深度优先搜索(DFS),广度优先搜索(BFS),最小生成树(MST)及Prim,Kruskal算法)

    图(Graph)是一种包含节点与节点的边的集合,记作G=(V,E),V是节点的集合,E是边的集合。 有向图 一个有向图G=(V,E),E中每个元素是V上的一个二值关系:一条从a出发的连向b的边e可以记作一个 有序 对e = (a,b) 。 无向图 一个无向图G=(V,E),E的每个元素e可以表示V上的一个 无序 对,记

    2024年02月03日
    浏览(52)
  • 迷宫问题-DFS-BFS

    🚀学习过算法程序设计的应该都学习过迷宫这个问题,迷宫问题主要设计的算法就是DFS-深度优先遍历和BFS-广度优先遍历。 🚀在一个二维数组中,元素为1的位置表示这个位置是墙,0表示有通路,迷宫的入口和出口都是0(否则不会有路径能出去),并且路径不唯一。例如下

    2023年04月22日
    浏览(45)
  • BFS算法(宽度优先搜索)超强解析 BFS迷宫问题图文详解 DFS与BFS的区别

      前情回顾:DFS练习-迷宫(最短路径)问题详解 一波三折 图片+文字 以及你需要会的基础:手搓数据结构之队列queue C/C++语言版(BFS算法预备知识) 广度优先搜索(Breadth First Search)简称广搜或者 BFS, 是遍历图存储结构的一种算法 。 BFS的原理是 “逐层扩散” ,从起点出发

    2024年02月22日
    浏览(48)
  • 【算法】(BFS/DFS)迷宫路径问题(C语言)

    题目 :现有一迷宫如下图所示,蓝色部分为墙壁,白色部分为通路,入口在左上角(1,1)处,出口在右下角(8,8)处,试找出一条路径以通过该迷宫(路径不能重叠)。 分析 : ① 使用二维数组来存储迷宫,墙用 1 表示,路用 0 表示,如下图所示: 为与题目中的入口坐标

    2024年02月07日
    浏览(83)
  • 迷宫问题:BFS(队列,最短路径)和DFS(栈

    搜索的基本算法分为两种:宽度优先搜索(Breadth-First Search,BFS)以及深度优先搜索(Depth-First Search,DFS)。 在学习过程中我们常常会遇到许多需要用搜索解决的问题。比如迷宫。 这次专题主要是对栈和队列的应用进行分析。所以首先我们先简要描述一下DFS和BFS方便大家对下

    2024年02月09日
    浏览(36)
  • 代码随想录| 图论02●695岛屿最大面积 ●1020飞地的数量 ●130被围绕的区域 ●417太平洋大西洋水流问题

    #695岛屿最大面积 模板题,很快.以下两种dfs,区别是看第一个点放不放到dfs函数中处理,那么初始化的area一个是1一个是0  bfs:对应也有两种 #1020飞地的数量 下面是自己写的dfs,过了但是很多可以改进。bfs也差不多这里就不写了  可改进的点: 1 其实遍历四周可以四个循环合

    2024年02月16日
    浏览(46)
  • 岛屿个数(dfs)

    小蓝得到了一副大小为 M × N M×N M × N 的格子地图,可以将其视作一个只包含字符 0 0 0 (代表海水)和 1 1 1 (代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上/下/左/右四个方向上相邻的 1 1 1 相连接而形成。 在岛屿 A 所占据的格子中,如果可以从中选

    2024年04月13日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包