首页 > 其他分享 >第十一章 图论 Part2

第十一章 图论 Part2

时间:2024-09-05 15:29:55浏览次数:13  
标签:图论 遍历 第十一章 self Part2 grid visited nextX nextY

目录

任务

200. 岛屿数量

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

思路

总的逻辑是,每遇到一个新的岛屿,就将计数加1,具体的遍历格子则使用dfs和bfs去遍历陆地,对于每一个格子,都进行dfs或bfs的遍历,

  1. 当前为水,不统计计数,继续下一个格子的处理
  2. 当前为已经遍历过的岛屿,不统计计数,继续下一个格子的处理
  3. 遇到新大陆(未访问过的大陆格子),则对该格子进行遍历以找到与该格子相关的整个岛屿
    具体单个岛屿的遍历,实现既可以用dfs,也可以用bfs。
    对于dfs,每遇到新的格子(未访问过的)且为陆地则标记并递归遍历,这里隐含着,如果遇到不是陆地的地方则进行下一个方向的处理。如此,可以访问一个整岛屿,将其相关格子标记为True。
    对于bfs,实际与bfs同理,只是遍历的流程是按照层去遍历,也是遍历一整个岛屿,将整个岛屿的格子标记为True。需要注意的点是,在每次加入队列时,都需要标记格子为True,原因是为了不重复访问,节省时间,具体更详细的原因可以去看第十一章 图论 Part1的内容。
    下面给出dfs和bfs解决这个问题的代码
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        visited =  [[False] * len(grid[0]) for _ in range(len(grid))]
        result = 0
        for i in range(len(grid)): #以每个格子为起点进行遍历
            for j in range(len(grid[0])):
                if visited[i][j]==False and grid[i][j] == '1': #为新大陆时,累加结果    
                    result += 1
                    #self.dfs(grid,visited,i,j) #按深度优先遍历标记某岛屿
                    self.bfs(grid,visited,i,j) #按深度优先遍历标记某岛屿
        return result

    def dfs(self,grid,visited,x,y):
        dir = [(1,0),(0,1),(-1,0),(0,-1)] #逆时针四个方向
        visited[x][y] = True # 由调用者(包含外部和自身)保证了该格子为访问过的陆地!
        
        for i in range(4):
            nextX = x + dir[i][0]
            nextY = y + dir[i][1]

            if nextX < 0 or nextY<0 or nextX>=len(grid) or nextY>=len(grid[0]):
                continue
            if visited[nextX][nextY] == False and grid[nextX][nextY] == '1':
                self.dfs(grid,visited,nextX,nextY)
    
    from collections import deque
    def bfs(self,grid,visited,x,y):
        dir = [(1,0),(0,1),(-1,0),(0,-1)] #逆时针四个方向
        que = deque()
        que.append((x,y))
        visited[x][y] = True

        while(que):
            curX,curY = que.popleft()
            
            for i in range(4):
                nextX = curX + dir[i][0]
                nextY = curY + dir[i][1]

                if nextX < 0 or nextY<0 or nextX>=len(grid) or nextY>=len(grid[0]):
                    continue
                if visited[nextX][nextY] == False and grid[nextX][nextY] == '1':
                    que.append((nextX,nextY))
                    visited[nextX][nextY] =True
            

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。

思路

如果理解了上一题,本题就可以直接解决,本题求的是岛屿面积,累计的值就是某一个岛屿的面积,就在dfs或者bfs中累计,然后在主函数中取最大的岛屿面积即可。
下面给出dfs和bfs的方法

class Solution:
    def __init__(self):
        self.count = 0
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        visited =  [[False] * len(grid[0]) for _ in range(len(grid))]
        result = 0
        for i in range(len(grid)): #以每个格子为起点进行遍历
            for j in range(len(grid[0])):
                if visited[i][j]==False and grid[i][j] == 1: #为新大陆时,累加结果    
                    self.count = 0
                    #self.dfs(grid,visited,i,j) #按深度优先遍历标记某岛屿
                    self.bfs(grid,visited,i,j) #按深度优先遍历标记某岛屿
                    result = max(result,self.count)
                   
        return result

    def dfs(self,grid,visited,x,y):
        dir = [(1,0),(0,1),(-1,0),(0,-1)] #逆时针四个方向
        visited[x][y] = True # 由调用者(包含外部和自身)保证了该格子为访问过的陆地!
        self.count += 1
        
        for i in range(4):
            nextX = x + dir[i][0]
            nextY = y + dir[i][1]

            if nextX < 0 or nextY<0 or nextX>=len(grid) or nextY>=len(grid[0]):
                continue
            if visited[nextX][nextY] == False and grid[nextX][nextY] == 1: #未访问过的陆地则继续访问(直到遍历完整个单独的岛屿)
                self.dfs(grid,visited,nextX,nextY)
    
    from collections import deque
    def bfs(self,grid,visited,x,y):
        dir = [(1,0),(0,1),(-1,0),(0,-1)] #逆时针四个方向
        que = deque()
        que.append((x,y))
        visited[x][y] = True
        self.count += 1

        while(que):
            curX,curY = que.popleft()
            
            for i in range(4):
                nextX = curX + dir[i][0]
                nextY = curY + dir[i][1]

                if nextX < 0 or nextY<0 or nextX>=len(grid) or nextY>=len(grid[0]):
                    continue
                if visited[nextX][nextY] == False and grid[nextX][nextY] == 1: #未访问过的陆地则继续访问(直到遍历完整个单独的岛屿)
                    que.append((nextX,nextY))
                    visited[nextX][nextY] =True
                    self.count+=1

标签:图论,遍历,第十一章,self,Part2,grid,visited,nextX,nextY
From: https://www.cnblogs.com/haohaoscnblogs/p/18398514

相关文章

  • 代码随想录day52 || 图论搜索 岛屿数量,岛屿的最大面积
    图遍历dfs深度优先搜索bfs广度优先搜索200岛屿数量(dfs)vardirPath=[][]int{{0,-1},{1,0},{0,1},{-1,0}}//上,右,下,左varvisited[][]boolfuncnumIslands(grid[][]byte)int{ //dfs深度优先遍历,对于每一个节点,按照上下左右四个固定顺序遍历,然后到下......
  • 搜索与图论
    这部分内容要用到树的数据结构,我们有以下几种方式来存储节点邻接表邻接表就是用类似链表的结构来存储数据,先创建一个数组h,每一个位置都有一个表头。然后e数组和ne数组分别表示节点的值是多少,节点的下一个节点的编号是多少,这种方式一般用在稠密图中,也就是节点数跟边数相差很大。......
  • 图论连通性相关
    并查集普通并查集:路径压缩写法:structUnion_Find_Set{ intf[N]; inlinevoidinit(){ for(inti=1;i<=n;++i) f[i]=i; } inlineintfind(intx){ if(x!=f[x])f[x]=find(f[x]); returnf[x]; } inlinevoidmerge(inta,intb){ intx......
  • Study Plan For Algorithms - Part21
    1.缺失的第一个正数题目链接:https://leetcode.cn/problems/first-missing-positive/给定一个未排序的整数数组nums,请找出其中没有出现的最小的正整数。classSolution:deffirstMissingPositive(self,nums:List[int])->int:n=len(nums)forii......
  • 代码随想录训练营 Day50打卡 图论part01 理论基础 98. 所有可达路径
    代码随想录训练营Day50打卡图论part01一、理论基础DFS(深度优先搜索)和BFS(广度优先搜索)在图搜索中的核心区别主要体现在搜索策略上:1、搜索方向:DFS:深度优先,一条路走到黑。DFS从起点开始,选择一个方向深入到底,遇到死胡同再回溯,换一个方向继续探索。这种方式适合解决路径......
  • [Python图论]在用图nx.shortest_path求解最短路径时,节点之间有多条边edge,会如何处理?
    问:在使用图求最短路径时,如果节点之间有多条路径,shortest_route=nx.shortest_path(G,source=start_node,target=end_node,weight='length')会如何处理,会自动选择最短那条吗?#输出图G各节点之间有多少条边edge,并给出其长度Edgesbetween103928and25508583:共2条Edge......
  • 第十一章 图论 Part1
    任务797.所有可能的路径给你一个有n个节点的有向无环图(DAG),请你找出所有从节点0到节点n-1的路径并输出(不要求按特定顺序)graph[i]是一个从节点i可以访问的所有节点的列表(即从节点i到节点graph[i][j]存在一条有向边)。思路题目所给的图的表示是邻接表,题意就是找到......
  • 代码随想录day50 || 图论基础
    图论基础定义图的构造方式1,邻接矩阵矩阵位置array[i][j]=k,i表示节点i,j表示节点j,[i][j]表示i-->j存在一条边,k表示的是边的权重邻接矩阵的优点:表达方式简单,易于理解检查任意两个顶点间是否存在边的操作非常快适合稠密图,在边数接近顶点数平方的图中,邻接矩阵是一种空......
  • 代码随想录 刷题记录-26 图论 (3)最小生成树
    一、prim算法精讲53.寻宝解题思路最小生成树是所有节点的最小连通子图,即:以最小的成本(边的权值)将图中所有节点链接到一起。图中有n个节点,那么一定可以用n-1条边将所有节点连接到一起。那么如何选择这n-1条边就是最小生成树算法的任务所在。例如本题示例中的无......
  • 代码随想录day16--图论
    题目描述:给定一个由1(陆地)和0(水)组成的矩阵,你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成,并且四周都是水域。你可以假设矩阵外均被水包围。输入描述:第一行包含两个整数N,M,表示矩阵的行数和列数。后续N行,每行包含M个数字,数字为1或者0。输出描......