【算法】图论中DFS和BFS模板讲解

news/2024/12/19 20:47:30/

        图论的解题模板和二叉树基本一致,都是在DFS和BFS基础上进行求解。
        二叉树的DFS和BFS模板如下所示:

public void DFSTree(TreeNode root){if(root==null)return null;DFSTree(root.left);DFSTree(root.right);
}
public void BFSTree(TreeNode root){if(root==null) return;Deque<TreeNode> queue=new ArrayDeque<>();queue.offer(root);while(!queue.isEmpty()){TreeNode curNode=queue.poll();if(curNode.left!=null){queue.offer(curNode.left);}if(curNode.right!=null){queue.offer(curNode.right);}}
}

        根据二叉树的DFS和BFS模板可以发现,整代码有两个要素:访问相邻结点和判断base case。

        由于二叉树本身是一个递归的定义,一颗二叉树它的左右子树也是一颗二叉树,因此访问相邻结点只需访问左右结点即可。

        而对DFS来说,base case就是root==null,这有两层含义:一是递归的终止条件,表示当前root指向的结点为空,要停止递归,不需要再往下遍历了。二是root==null表示遍历到了叶子结点,应及时返回,避免出现root.leftroot.right空指针异常。而对BFS来说,base case就是while(!queue.isEmpty())curNode.left!=nullcurNode.right!=nullwhile(!queue.isEmpty())表示当前队列不为空,即还需要继续遍历,而curNode.left!=nullcurNode.right!=null则保证入队的元素均不为空。

        类比二叉树的特性,可以写出图中DFS和BFS的两个要素:1、图中某个格子的相邻结点是什么?该如何访问?2、判断base case。

        对于格子(row,col)来说,它的相邻结点分别在上下左右,分别为(row-1,col)、(row+1,col)、(row,col-1)、(row,col+1),其次类比二叉树通过root==null来充当base case确保不需要继续遍历,那么在图中的base case应该就是出现数组越界的格子,这样就能得到图论中DFS和BFS的基础架构

public void DFSGrid(int[][] grid,int row,int col){// 判断 base caseif(row<0||col<0||row>=grid.length||col>=grid[0].length)return;// 访问上、下、左、右四个相邻结点DFSGrid(grid,row-1,col);DFSGrid(grid,row+1,col);DFSGrid(grid,row,col-1);DFSGrid(grid,row,col+1);
}
public void BFSGrid(int[][] grid,int row,int col){Deque<int[]> queue=new ArrayDeque<>();queue.offer(new int[]{row,col});//处理当前格子等操作grid[row][col]=已遍历while(!queue.isEmpty()){int[] cur=queue.poll();row=cur[0];col=cur[1];//判断base caseif(row>=0&&col>=0&&row<grid.length&&col<grid[0].length){//记录当前格子等操作grid[row][col]=已遍历// 访问上、下、左、右四个相邻结点queue.offer(new int[]{row-1,col});queue.offer(new int[]{row+1,col});queue.offer(new int[]{row,col-1});queue.offer(new int[]{row,col+1});}}
}

        在不熟悉的情况下,可能会疑惑为什么DFS(grid,row,col)和queue.offer(grid,new int[]{row-1,col})时不用判断参数是否合法?难度不会数组越界吗?其实可以先合法性判断,然后再进行DFS和BFS,但是我们用的方法是先使用后判断,将判断的操作统一放在前面,这样在取上下左右四个位置的时候不用判断四次参数的合理性,而是先将其视为合法的进行保存,然后在要访问的时候在统一判断合法性,避免了多次冗余的判断。
        其次对于BFS的queue中为什么要存坐标,是因为通过坐标可以直接访问到对应的格子,同时更改坐标可以快速定位到其上下左右四个格子,若存储格子,那如何传递参数来访问上下左右四个格子呢?


http://www.ppmy.cn/news/1556474.html

相关文章

免费开源了一个图床工具 github-spring-boot-starter

文章目录 第一步&#xff0c;新建一个SpringBoot项目第二步&#xff0c;在pom文件里面引入jar包第三步&#xff0c;配置你的github信息github.authorization1、进入github官网&#xff0c;登录账号&#xff0c;点击头像&#xff0c;选择setting2、选择[Developer Settings](htt…

[Unity Shader] 【游戏开发】Unity Shader的结构2-深入理解 SubShader 的结构与应用

在 Unity 中,Shader 是图形渲染管线中的核心组件,而 SubShader 是 Shader 结构中不可或缺的部分。每个 Unity Shader 文件可以包含多个 SubShader,它们根据不同的显卡和硬件条件提供不同的渲染实现。本文将详细介绍 SubShader 的结构、标签(Tags)、渲染设置(RenderSetup)…

Android14 AOSP支持短按关机

修改frameworks/base/services/core/java/com/android/server/policy/PhoneWindowManager.java diff --git a/base/services/core/java/com/android/server/policy/PhoneWindowManager.java b/base/services/core/java/com/android/server/policy/PhoneWindowManager.java in…

电脑文档损坏:原因剖析和修复方法

在使用电脑的过程中&#xff0c;许多用户可能会遇到文档突然提示损坏、无法打开的情况。这种情况的发生往往让人感到困惑&#xff0c;特别是当并未进行任何明显错误操作时。以下是一些常见的原因以及应对方法。 一、文档损坏的常见原因 1、非人为的异常操作&#xff1a; 在编…

碰一碰发视频 + 智能文案生成全解析,支持OEM

一、引言 在数字化营销的汹涌浪潮中&#xff0c;新颖且高效的推广策略不断迭代涌现。“碰一碰发视频” 结合 “点评打卡、种草文案一键生成” 的创新模式&#xff0c;宛如一颗璀璨的营销新星&#xff0c;正以燎原之势重塑商家与消费者的互动生态&#xff0c;为品牌传播及用户引…

低延迟!实时处理!中软高科AI边缘服务器,解决边缘计算多样化需求!

根据相关统计&#xff0c;随着物联网的发展和5G技术的普及&#xff0c;到2025年&#xff0c;全球物联网设备连接数将达到1000亿&#xff0c;海量的计算数据使得传输到云端再处理的云计算方式显得更捉襟见肘。拥有低延迟、实时处理、可扩展性和更高安全性的边缘计算应运而生&…

linux redhat9系统 交互和非交互设定延时任务

1.交互延时任务的设定 at now&#xff08;时间&#xff09; “需要执行的任务” ctrlz开始执行 2.非交互延时任务的设定 vim编写脚本 设置输出重定向 输出重定向之间写需要进行的操作 之后 sh test.sh执行 2.延时任务黑白名单 由于所有用户模式下都可以设定延时任务 所…

剑指Offer|LCR 002. 二进制求和

LCR 002. 二进制求和 给定两个 01 字符串 a 和 b &#xff0c;请计算它们的和&#xff0c;并以二进制字符串的形式输出。 输入为 非空 字符串且只包含数字 1 和 0。 示例 1: 输入: a "11", b "10" 输出: "101"提示&#xff1a; 每个字符串…