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

ops/2024/12/19 22:51:04/

        图论的解题模板和二叉树基本一致,都是在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/ops/143304.html

相关文章

Javascript面试手撕常见题目(回顾一)

1.JS查找文章中出现频率最高的单词? 要在JavaScript中查找文章中出现频率最高的单词&#xff0c;你可以按照以下步骤进行操作&#xff1a; 将文章转换为小写&#xff1a;这可以确保单词的比较是大小写不敏感的。移除标点符号&#xff1a;标点符号会干扰单词的计数。将文章拆…

前端 下载文件时如何处理后端返回的 文件流

在前端&#xff0c;处理文件下载通常涉及到接受一个 文件流&#xff08;Blob 或者 ArrayBuffer&#xff09;&#xff0c;然后将它转换成可以下载的链接。以下是实现前端文件下载并接受文件流的一些常见方法。 1. 使用 Blob 和 URL.createObjectURL 创建下载链接 假设后端返回…

Web 毕设篇-适合小白、初级入门练手的 Spring Boot Web 毕业设计项目:电影院后台管理系统(前后端源码 + 数据库 sql 脚本)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 项目介绍 2.0 用户登录功能 3.0 用户管理功能 4.0 影院管理功能 5.0 电影管理功能 6.0 影厅管理功能 7.0 电影排片管理功能 8.0 用户评论管理功能 9.0 用户购票功…

Redis 数据备份与恢复

Redis 数据备份与恢复 1. 引言 Redis 作为一款高性能的键值数据库,被广泛应用于各种场景,如缓存、消息队列等。由于其重要性,对 Redis 数据进行定期备份是保证数据安全的关键措施。本文将详细介绍 Redis 数据的备份与恢复方法,确保在数据丢失或系统故障时能够迅速恢复。 …

开源FreeSWITCH大模型智能客服系统的最佳实践

开源 FreeSWITCH 大模型智能客服系统的最佳实践 原作者&#xff1a;开源呼叫中心FreeIPCC&#xff0c;其Github&#xff1a;https://github.com/lihaiya/freeipcc 引言 开源 FreeSWITCH 大模型智能客服系统因其灵活性、成本效益和技术先进性&#xff0c;成为众多企业提升客户…

封装confirm(Vue3+Ts)

文章目录 思路createApp封装confirm下周计划 思路 封装confirm首先要在以前js封装confirm的基础上进行操作 之前封装confirm的时候 是通过调用自己写的confirm函数实现弹窗的出现以及消失并进行逻辑的 那么在Vue3中怎么实现呢&#xff1f; 首先要进行调用函数进行传参的操作&a…

Vite 系列课程|3.Vite 相较于 Webpack 的优势

3. Vite 相较于 Webpack 的优势 参考官方文档&#xff1a;https://cn.vitejs.dev/guide/why.html#the-problems Vite 的出现并非偶然&#xff0c;它是为了解决 Webpack 在现代前端开发中逐渐暴露出的瓶颈而诞生的。主要体现在构建效率、开发体验、配置复杂度等方面。 3.1 构…

华为OD E卷(100分)22-机器人的活动区域

前言 工作了十几年&#xff0c;从普通的研发工程师一路成长为研发经理、研发总监。临近40岁&#xff0c;本想辞职后换一个相对稳定的工作环境一直干到老, 没想到离职后三个多月了还没找到工作&#xff0c;愁肠百结。为了让自己有点事情做&#xff0c;也算提高一下自己的编程能力…