【优选算法之BFS】No.16---多源BFS和BFS解决拓扑排序

embedded/2024/10/11 0:15:54/

文章目录

  • 前言
  • 一、多源BFS示例：
    • 1.1 01 矩阵
    • 1.2 ⻜地的数量
    • 1.3 地图中的最⾼点
    • 1.4 地图分析
  • 二、BFS解决拓扑排序：
    • 2.1 拓扑排序简介
      • 2.1.1 有向无环图(DAG图)
      • 2.1.2 AVO网：顶点活动图
      • 2.1.3 拓扑排序
      • 2.1.4 实现拓扑排序
    • 2.2 BFS解决拓扑排序示例：
      • 2.2.1 课程表
      • 2.2.2 课程表 II
      • 2.2.3 ⽕星词典

前言

在这里插入图片描述

👧个人主页：@小沈YO.
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：优选算法
🔑本章内容：多源BFS和BFS解决拓扑排序
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~

一、多源BFS示例：

1.1 01 矩阵

  1. 题⽬链接：542. 01 矩阵
  2. 题⽬描述：
    在这里插入图片描述
  3. 解法（bfs）（多个源头的最短路问题）
    算法思路：对于求的最终结果，我们有两种⽅式：
    • 第⼀种⽅式：从每⼀个 1 开始，然后通过层序遍历找到离它最近的 0 。
    这⼀种⽅式，我们会以所有的 1 起点，来⼀次层序遍历，势必会遍历到很多重复的点。并且如果矩阵中只有⼀个 0 的话，每⼀次层序遍历都要遍历很多层，时间复杂度较⾼。
    • 换⼀种⽅式：从 0 开始层序遍历，并且记录遍历的层数。当第⼀次碰到 1 的时候，当前的层数就是这个 1 离 0 的最短距离。 这⼀种⽅式，我们在遍历的时候标记⼀下处理过的 1 ，能够做到只⽤遍历整个矩阵⼀次，就能得到最终结果。
    但是，这⾥有⼀个问题， 0 是有很多个的，我们怎么才能保证遇到的 1 距离这⼀个 0 是最近的呢？
    其实很简单，我们可以先把所有的 0 都放在队列中，把它们当成⼀个整体，每次把当前队列⾥⾯的所有元素向外扩展⼀次。
  4. C++代码
class Solution {int n,m;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};
public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {n=mat.size();m=mat[0].size();queue<pair<int,int>> q;vector<vector<int>> vv(n,vector<int>(m,-1));for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(mat[i][j]==0){vv[i][j]=0;q.push({i,j});}}}int cnt=0;while(!q.empty()){int sz=q.size();cnt++;while(sz--){auto[a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&vv[x][y]==-1){vv[x][y]=cnt;q.push({x,y});                        }}}}return vv;}
};

1.2 ⻜地的数量

  1. 题⽬链接：1020. ⻜地的数量
  2. 题⽬描述：
    在这里插入图片描述
  3. 解法：
    算法思路：
    正难则反：
    从边上的 1 开始搜索，把与边上 1 相连的联通区域全部标记⼀下； 标记的时候，可以⽤「多源 bfs 」解决。
  4. C++代码
class Solution {int n,m;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int vis[510][510]={0};int ret=0;
public:int numEnclaves(vector<vector<int>>& grid) {n=grid.size(),m=grid[0].size();queue<pair<int,int>> q;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(grid[i][j]==1)ret++;for(int i=0;i<n;i++){if(grid[i][0]==1&&!vis[i][0]){q.push({i,0});vis[i][0]=1;ret--;}if(grid[i][m-1]==1&&!vis[i][m-1]){q.push({i,m-1});vis[i][m-1]=1;ret--;}}for(int i=0;i<m;i++){if(grid[0][i]==1&&!vis[0][i]){q.push({0,i});vis[0][i]=1;ret--;}if(grid[n-1][i]==1&&!vis[n-1][i]){q.push({n-1,i});vis[n-1][i]=1;ret--;}}while(!q.empty()){int sz=q.size();while(sz--){auto[a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1&&!vis[x][y]){q.push({x,y});vis[x][y]=1;ret--;}}}}return ret;}
};

1.3 地图中的最⾼点

  1. 题⽬链接：1765. 地图中的最⾼点
  2. 题⽬描述：
    在这里插入图片描述
  3. 解法：
    算法思路：
    01矩阵的变型题，直接⽤多源 bfs 解决即可。
  4. C++代码
class Solution {int n,m;int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};
public:vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {n=isWater.size();m=isWater[0].size();vector<vector<int>> height(n,vector<int>(m,-1));queue<pair<int,int>> q;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(isWater[i][j]==1){height[i][j]=0;q.push({i,j});}}}int cnt=0;while(!q.empty()){int sz=q.size();cnt++;while(sz--){auto[a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&height[x][y]==-1){height[x][y]=cnt;q.push({x,y});}}}}      return height;}
};

1.4 地图分析

  1. 题⽬链接：1162. 地图分析
  2. 题⽬描述：
    在这里插入图片描述
  3. 解法：
    算法思路：
    01矩阵的变型题，直接⽤多源 bfs 解决即可。
  4. C++代码
class Solution {int n;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int maxlen=0,cnt=0;;int vis[110][110]={0};
public:int maxDistance(vector<vector<int>>& grid) {n=grid.size();queue<pair<int,int>> q;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){vis[i][j]=1;q.push({i,j});}}}if(q.size()==0||q.size()==n*n)return -1;while(!q.empty()){int sz=q.size();cnt++;while(sz--){auto[a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<n&&!vis[x][y]){q.push({x,y});vis[x][y]=1;maxlen=max(maxlen,cnt);}}}}return maxlen;}
};

二、BFS解决拓扑排序：

2.1 拓扑排序简介

2.1.1 有向无环图(DAG图)

在这里插入图片描述
上述图中绿色表示入度（箭头指向），红色表示出度（箭头指出）。

2.1.2 AVO网：顶点活动图

在有向无环图中，用顶点来表示一个活动，用边来表示活动的先后顺序的图结构

2.1.3 拓扑排序

找到做事情的先后顺序，拓扑排序的结果可能不是唯一的。
如何排序？

  1. 找出图中入度为0的点，然后输出
  2. 删除与该点连接的边
  3. 重复上述1 2操作，直到图中没有点或者没有入度为0的点

重要应用：判断图中是否有环

2.1.4 实现拓扑排序

借助队列，来一次BFS即可。

  1. 初始化：把所有入度为0的点加入到队列中
  2. 当队列不为空的时候
    <1> 拿出队头元素，加入到最终结果中
    <2> 删除与该元素相连的边（这里的边也就是与删除节点相连的结点的入度）
    <3> 判断：与删除边相连的点，是否入度变成0，如果入度为0，加入到队列中

2.2 BFS解决拓扑排序示例：

2.2.1 课程表

  1. 题⽬链接：207. 课程表
  2. 题⽬描述：
    在这里插入图片描述
  3. 解法：
    算法思路：
    原问题可以转换成⼀个拓扑排序问题。⽤ BFS 解决拓扑排序即可。
    拓扑排序流程：
    a. 将所有⼊度为 0 的点加⼊到队列中；
    b. 当队列不空的时候，⼀直循环：
    i. 取出队头元素；
    ii. 将于队头元素相连的顶点的⼊度 - 1；
    iii. 然后判断是否减成 0,。如果减成 0，就加⼊到队列中。
  4. C++代码
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//1.创建邻接表unordered_map<int,vector<int>> edges;//入度vector<int> in(numCourses);for(auto&e:prerequisites){int a=e[0],b=e[1];edges[b].push_back(a);in[a]++;}//将入度为0的点插入到队列中queue<int> q;for(int i=0;i<numCourses;i++){if(in[i]==0)q.push(i);}//循环while(!q.empty()){int sz=q.size();while(sz--){auto tmp=q.front();q.pop();for(auto&e:edges[tmp])//找到对应的点将入度--{if(--in[e]==0)q.push(e);//判断入度是否为0，为0则加入队列}}}//判断一下入度是否都为0，如果都为0则表示没有环可以完成，否则有环for(int i=0;i<numCourses;i++){if(in[i])return false;}return true;}
};

2.2.2 课程表 II

  1. 题⽬链接：210. 课程表 II
  2. 题⽬描述：
    在这里插入图片描述
  3. 解法：
    算法思路：
    和上⼀题⼀样~ 只不过需要添加一个vector数组来添加入度为0的课程
  4. C++代码
class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int> cs;//创建邻接表+入度unordered_map<int,vector<int>> edges;vector<int> in(numCourses);for(auto&e:prerequisites){int a=e[0],b=e[1];edges[b].push_back(a);in[a]++;}//遍历查找入度为0的点加入到队列queue<int> q;for(int i=0;i<numCourses;i++){if(in[i]==0)q.push(i);}//循环while(!q.empty()){int sz=q.size();while(sz--){auto tmp=q.front();q.pop();cs.push_back(tmp);for(auto&e:edges[tmp]){if(--in[e]==0)q.push(e);}}}//判环for(int i=0;i<numCourses;i++){if(in[i]){cs.clear();}}return cs;}
};

2.2.3 ⽕星词典

  1. 题⽬链接：LCR 114. ⽕星词典
  2. 题⽬描述：
    在这里插入图片描述
  3. 解法：
    算法思路：
    将题意搞清楚之后，这道题就变成了判断有向图时候有环，可以⽤拓扑排序解决。
    如何搜集信息（如何建图）：
    a. 两层 for 循环枚举出所有的两个字符串的组合；
    b. 然后利⽤指针，根据字典序规则找出信息
  4. C++代码
class Solution {unordered_map<char,unordered_set<char>> edges;unordered_map<char,int>in;bool check=false;
public:void Add(const string& s1,const string& s2){int n=min(s1.size(),s2.size());int i=0;for(i=0;i<n;i++){if(s1[i]!=s2[i]){char a=s1[i],b=s2[i];if(!edges.count(a)||!edges[a].count(b)){edges[a].insert(b);in[b]++;}break;}}if(i==s2.size()&&i<s1.size())check=true;//s1="abc"  s2="ab" 是不合法的将check设置为true}string alienOrder(vector<string>& words) {string s;for(auto&s:words){for(auto&ch:s)in[ch]=0;}for(int i=0;i<words.size();i++){for(int j=i+1;j<words.size();j++){Add(words[i],words[j]);if(check)return "";//check==true直接返回空字符不合法即可}}queue<char> q;for(auto[a,b]:in){if(b==0)q.push(a);}while(!q.empty()){int sz=q.size();while(sz--){auto tmp=q.front();q.pop();s+=tmp;for(auto&e:edges[tmp]){if(--in[e]==0)q.push(e);}}}for(auto[a,b]:in){if(b)return "";}return s;}
};

http://www.ppmy.cn/embedded/125620.html

相关文章

AAA Mysql与redis的主从复制原理

AAA Mysql与redis的主从复制原理

一 &#xff1a;Mysql主从复制 重要的两个日志文件&#xff1a;bin log 和 relay log bin log&#xff1a;二进制日志&#xff08;binnary log&#xff09;以事件形式记录了对MySQL数据库执行更改的所有操作。 relay log&#xff1a;用来保存从节点I/O线程接受的bin log日志…
阅读更多...
髓质脊髓三叉神经核文献阅读笔记

髓质脊髓三叉神经核文献阅读笔记

文献阅读 1.RNA-seq 对于大量RNA测序&#xff0c;收集第30天的类器官。使用FastPure细胞/组织总RNA分离试剂盒根据制造商的方案提取总RNA。采用Nanodrop 2000分光光度计测定RNA浓度和纯度。使用Agilent 2100生物分析仪和2100 RNA纳米6000检测试剂盒评估RNA样品的完整性。简单…
阅读更多...
面试--开源框架面试题集合

面试--开源框架面试题集合

Spring 谈谈自己对于 Spring IoC 的了解什么是 IoC?IoC 解决了什么问题?什么是 Spring Bean&#xff1f;将一个类声明为 Bean 的注解有哪些?Component 和 Bean 的区别是什么&#xff1f;注入 Bean 的注解有哪些&#xff1f;Autowired 和 Resource 的区别是什么&#xff1f;…
阅读更多...
EcoVadis认证内容有哪些？EcoVadis认证申请流程？

EcoVadis认证内容有哪些？EcoVadis认证申请流程？

EcoVadis认证是一个国际性的可持续发展评估平台&#xff0c;旨在帮助全球企业和供应链评鉴其在环境、社会和治理&#xff08;ESG&#xff09;方面的表现。该认证框架由法国的检验、认证和检测机构必维集团&#xff08;Bureau Veritas&#xff09;创建&#xff0c;得到了众多跨国…
阅读更多...
【STM32单片机_(HAL库)】4-5-3【定时器TIM】【感应开关盖垃圾桶项目】项目实现

【STM32单片机_(HAL库)】4-5-3【定时器TIM】【感应开关盖垃圾桶项目】项目实现

1.项目需求 以下几个事件触发时&#xff0c;垃圾桶自动开盖&#xff0c;并伴随蜂鸣器短响一声&#xff0c;同时 LED 灯闪烁一下&#xff0c;2秒后自动关盖&#xff1a; 检测到有人靠近检测到有震动按下按键 KEY1 2.硬件 STM32单片机最小系统震动传感器模块蜂鸣器模块&#…
阅读更多...
Jensen-Shannon散度（JS散度）

Jensen-Shannon散度（JS散度）

Jensen-Shannon散度&#xff08;Jensen-Shannon Divergence, JS散度&#xff09;是概率分布之间的一种相似性度量。它是基于Kullback-Leibler散度&#xff08;KL散度&#xff09;的对称版本&#xff0c;并且具有一些更好的性质&#xff0c;例如它总是非负的&#xff0c;并且是有…
阅读更多...
Luminar财务造假风波：激光雷达龙头的困境与挑战

Luminar财务造假风波：激光雷达龙头的困境与挑战

近日，美国激光雷达上市公司Luminar被爆出财务造假嫌疑，这一消息震惊了整个行业。Luminar，这家曾风光无限的激光雷达公司，最高市值一度达到120亿美元，其年轻的创始人也因此坐拥豪宅豪车无数。然而，如今在市值仅剩5亿美元左右的时候，却被爆出如此丑闻，令人不禁唏嘘。 带…
阅读更多...
软考《信息系统运行管理员》- 4.4 信息系统软件运维系统与专用工具

软考《信息系统运行管理员》- 4.4 信息系统软件运维系统与专用工具

4.4 信息系统软件运维系统与专用工具 文章目录 4.4 信息系统软件运维系统与专用工具信息系统软件运维系统的功能信息系统软件信息采集信息系统软件监控信息系统软件分发功能 信息系统软件运维专用工具 信息系统软件运维系统的功能 信息系统软件信息采集 可以快速查询网络内各…
阅读更多...
最新文章

Copyright @ 2022~2023