当前位置: 首页 > news >正文

BFS 算法专题(五):BFS 解决拓扑排序

目录

1. 拓扑排序简介

1.1 有向无环图 (DAG 图)

1.2 AOV 网(顶点活动图)

1.3 拓扑排序

1.3.1 如何实现

2. 力扣实战应用

2.1 课程表

 2.1.1 算法原理

2.1.2 算法代码

2.2 课程表 II

 2.2.1 算法原理

2.2.2 算法代码

2.3 火星词典 (hard) (原剑指offer)

2.3.1 算法原理

2.3.2 算法代码


1. 拓扑排序简介

1.1 有向无环图 (DAG 图)

顶点与顶点之间的边, 是具有方向, 并且不会构成环(无回路).

有向图中, 有两个重要概念:

  1. 出度
  2. 入度

1.2 AOV 网(顶点活动图)

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

1.3 拓扑排序

找到做的事情(活动)的先后顺序(可能不是唯一的).

排序过程:

  1. 找到入度为 1 的点
  2. 删除与该点连接的边
  3. 重复 1, 2 操作, 直至图中没有点或者没有入度为 0 的点(可能存在环)

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

1.3.1 如何实现

借助队列, 进行一次 BFS:

初始化: 把所有入度为 0 的点加入到队列中

当队列不为空时:

  1. 拿出队头元素, 加入已排序序列
  2. 删除与该元素相连接的边
  3. 判断: 与删除边相连的点, 是否入度为 0 , 若是, 则加入队列中

2. 力扣实战应用

2.1 课程表

. - 力扣(LeetCode)

 2.1.1 算法原理

问题核心: 判断 "图" 中是否带环 => 拓扑排序

灵活使用 Java 提供的集合类, 进行图的构建:

  1. 构建邻接表 => 1. List<List<Integer>> 2. Map<Integer, List<Integer>>

借助队列, 进行 BFS , 判断是否带环:

  1. 将所有入度为 0 的节点入队(从图中拿走该节点)
  2. 拿出队头元素, 删除与该元素相邻的边
  3. 判断与删除的边相连的节点入度是否为 0
  4. 若为 0 , 则入队
  5. 重复以上操作
  6. 当队空时, 若还有入度不为 0 的节点, 则说明该图带环

注意: 使用数组记录各节点的入度 => int[] in

2.1.2 算法代码

class Solution {public boolean canFinish(int n, int[][] p) {// 记录节点的入度int[] in = new int[n];// 构建邻接表Map<Integer, List<Integer>> edges = new HashMap<>();for(int i = 0; i < p.length; i++) {int a = p[i][0], b = p[i][1]; // b -> aif(!edges.containsKey(b)) {edges.put(b, new ArrayList<>());}edges.get(b).add(a);in[a]++;}Queue<Integer> q = new LinkedList<>();// 将入度为 0 的节点入队for(int i = 0; i < n; i++) {if(in[i] == 0) q.offer(i);}// bfswhile(!q.isEmpty()) {int t = q.poll();for(int x : edges.getOrDefault(t, new ArrayList<>())) {in[x]--;if(in[x] == 0) q.offer(x);}}for(int x : in) {if(x != 0) return false;}return true;}
}

2.2 课程表 II

. - 力扣(LeetCode)

 2.2.1 算法原理

本题解法与上题解法一致, 唯一需要多处理的就是记录拓扑排序的序列.

2.2.2 算法代码

class Solution {public int[] findOrder(int n, int[][] p) {// 统计节点的入度情况int[] in = new int[n + 1];// 创建邻接表Map<Integer, List<Integer>> edges = new HashMap<>();for(int i = 0; i < p.length; i++) {int a = p[i][0], b = p[i][1]; // b -> ain[a]++;if(!edges.containsKey(b)) {edges.put(b, new ArrayList<>());}edges.get(b).add(a);}Queue<Integer> q = new LinkedList<>();// 将入度为 0 的节点入队for(int i = 0; i < n; i++) {if(in[i] == 0) q.offer(i);}int size = 0;int[] ret = new int[n];// bfswhile(!q.isEmpty()) {int t = q.poll();// 进入拓扑序列ret[size++] = t;for(int x : edges.getOrDefault(t, new ArrayList<>())) {in[x]--;if(in[x] == 0) q.offer(x);}}return size == n ? ret : new int[]{};}
}

2.3 火星词典 (hard) (原剑指offer)

. - 力扣(LeetCode)

2.3.1 算法原理

  1. 统计节点的入度信息 => Map<Character, Integer> ; 将每个节点的入度信息初始化为 0 

  2. 构建邻接表 => Map<Character, Set<Character>> ; 注意不能重复接入存在的元素(所以使用 HashSet, 查找速度快)

  3. 搜集顺序信息 => 两层 for 循环 + 前后指针

  4. 细节问题 => "abc" "ab" , 这种特殊情况不合法, return "";

2.3.2 算法代码

class Solution {public String alienOrder(String[] words) {// 统计每个字符的入度Map<Character, Integer> in = new HashMap<>();for(String s : words) {for(int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if(!in.containsKey(ch)) in.put(ch, 0);}}// 构建邻接表Map<Character, Set<Character>> edges = new HashMap<>();for(int i = 0; i < words.length; i++) {for(int j = i + 1; j < words.length; j++) {int front = 0, tail = 0;String s1 = words[i], s2 = words[j];while(front < s1.length() && tail < s2.length()) {char ch1 = s1.charAt(front), ch2 = s2.charAt(tail);if(ch1 == ch2) {front++;tail++;}else {// ch1 -> ch2// 可能重复存在 : ch1 -> ch2if(edges.containsKey(ch1) && edges.get(ch1).contains(ch2)) {break;} if(!edges.containsKey(ch1)) {edges.put(ch1, new HashSet<>());}// 入度加一in.put(ch2, in.get(ch2) + 1);// 放入邻接表edges.get(ch1).add(ch2);break;}}// 字符串不合法if(front < s1.length() && tail >= s2.length()) return ""; }}Queue<Character> q = new LinkedList<>();StringBuilder stringBuilder = new StringBuilder();// 将入度为 0 的节点入队for(Map.Entry<Character, Integer> e : in.entrySet()) {if(e.getValue() == 0) q.offer(e.getKey());}// bfswhile(!q.isEmpty()) {char ch = q.poll();stringBuilder.append(ch);Set<Character> set = edges.getOrDefault(ch, new HashSet<>());for(Character x : set) {in.put(x, in.get(x) - 1);if(in.get(x) == 0) q.offer(x);}}for(Map.Entry<Character, Integer> e : in.entrySet()) {if(e.getValue() != 0) return "";}return stringBuilder.toString();}
}

END

相关文章:

BFS 算法专题(五):BFS 解决拓扑排序

目录 1. 拓扑排序简介 1.1 有向无环图 (DAG 图) 1.2 AOV 网(顶点活动图) 1.3 拓扑排序 1.3.1 如何实现 2. 力扣实战应用 2.1 课程表 2.1.1 算法原理 2.1.2 算法代码 2.2 课程表 II 2.2.1 算法原理 2.2.2 算法代码 2.3 火星词典 (hard) (原剑指offer) 2.3.1 算法原理…...

【Mysql】开窗聚合函数----SUM,AVG, MIN,MAX

1、概念 在窗口中&#xff0c;每条记录动态地应用聚合函数&#xff08;如&#xff1a;SUM(),AVG(),MAX(),MIN(),COUNT(),&#xff09;可以动态计算在指定的窗口内的各种聚合函数值。 2、操作 以下操作将基于employee表进行操作。 sum() 进行sum的时候&#xff0c;没有order …...

java操作doc——java利用Aspose.Words操作Word文档并动态设置单元格合并

在实际工作中&#xff0c;如果业务线是管理类项目或者存在大量报表需要导出的业务时&#xff0c;可以借助第三方插件实现其对应功能。 尤其是需要对word文档的动态操作或者模板数据的定向合并&#xff0c;使用Aspose会相对来说容易一些&#xff0c;而且相关文档比较完整&#…...

探索 .NET 9 控制台应用中的 LiteDB 异步 CRUD 操作

本文主要是使用异步方式&#xff0c;体验 litedb 基本的 crud 操作。 LiteDB 是一款轻量级、快速且免费的 .NET NoSQL 嵌入式数据库&#xff0c;专为小型本地应用程序设计。它以单一数据文件的形式提供服务&#xff0c;支持文档存储和查询功能&#xff0c;适用于桌面应用、移动…...

《进程隔离机制:C++多进程编程安全的坚固堡垒》

在当今数字化时代&#xff0c;软件系统的安全性愈发成为人们关注的焦点。尤其是在 C多进程编程领域&#xff0c;如何确保进程间的安全交互与数据保护&#xff0c;是每一位开发者都必须面对的重要课题。而进程隔离机制&#xff0c;犹如一座坚固的堡垒&#xff0c;为 C多进程编程…...

构建无障碍的数字世界:深入探讨Web可访问性指南

文章目录 前言一、什么是Web可访问性&#xff1f;二、Web内容无障碍指南&#xff08;WCAG&#xff09;三、ARIA属性的应用四、实践中的Web可访问性结语 前言 在当今高度互联的世界里&#xff0c;互联网已成为人们日常生活不可或缺的一部分。然而&#xff0c;对于数百万残障人士…...

跨境出海安全:如何防止PayPal账户被风控?

今天咱们聊聊那些让人头疼的事儿——PayPal账户被风控。不少跨境电商商家反馈&#xff0c;我们只是想要安安静静地在网上做个小生意&#xff0c;结果不知道为什么&#xff0c;莫名其妙账户就被冻结了。 但其实每个封禁都是有原因的&#xff0c;今天就来给大家分享分享可能的原…...

学习日记_20241123_聚类方法(MeanShift)

前言 提醒&#xff1a; 文章内容为方便作者自己后日复习与查阅而进行的书写与发布&#xff0c;其中引用内容都会使用链接表明出处&#xff08;如有侵权问题&#xff0c;请及时联系&#xff09;。 其中内容多为一次书写&#xff0c;缺少检查与订正&#xff0c;如有问题或其他拓展…...

AI编程和AI绘画哪个更适合创业?

AI编程和AI绘画各有优势&#xff0c;适合创业的方向取决于你的资源、兴趣、市场需求和技术能力。以下是两者的对比分析&#xff0c;帮助你选择更适合的方向&#xff1a; AI编程 优势 1、广泛应用领域&#xff1a; 涉及自动化、数据分析、自然语言处理、计算机视觉等多个领域&a…...

macOS 无法安装第三方app,启用任何来源的方法

升级新版本 MacOS 后&#xff0c;安装下载的软件时&#xff0c;不能在 ”安全性与隐私” 中找不到 ”任何来源” 选项。 1. 允许展示任何来源 点击 启动器 (Launchpad) – 其他 (Other) – 终端 (Terminal)&#xff1a; 打开终端后&#xff0c;输入以下代码回车&#xff1a; …...

关于SpringBoot集成Kafka

关于Kafka Apache Kafka 是一个分布式流处理平台&#xff0c;广泛用于构建实时数据管道和流应用。它能够处理大量的数据流&#xff0c;具有高吞吐量、可持久化存储、容错性和扩展性等特性。 Kafka一般用作实时数据流处理、消息队列、事件架构驱动等 Kafka的整体架构 ZooKeeper:…...

4.STM32之通信接口《精讲》之IIC通信---软件实现IIC《深入浅出》面试必备!

接下正式&#xff0c;进入软件编写IIC时序了&#xff0c;并实现对MPU6050的控制&#xff0c;既然是软件实现&#xff0c;那么硬件方面&#xff0c;我仅需两根控制线即可&#xff0c;即&#xff1a;数据控制线SDA&#xff0c;时钟控制线SCL。&#xff08;人为软件层面定义的&…...

6G通信技术对比5G有哪些不同?

6G&#xff0c;即第六代移动通信技术&#xff0c;是5G之后的延伸&#xff0c;代表了一种全新的通信技术发展方向。与5G相比&#xff0c;6G在多个方面都有显著的不同和提升&#xff0c;以下是对6G通信技术及其与5G差异的详细分析&#xff1a; 一、6G的基本特点 更高的传输速率…...

「Mac玩转仓颉内测版28」基础篇8 - 元组类型详解

本篇将介绍 Cangjie 中的元组类型&#xff0c;包括元组的定义、创建、访问、数据解构以及应用场景&#xff0c;帮助开发者掌握元组类型的使用。 关键词 元组类型定义元组创建元组访问数据解构应用场景 一、元组类型概述 在 Cangjie 中&#xff0c;元组是一种用于存储多种数据…...

WebStorm 2024.3/IntelliJ IDEA 2024.3出现elementUI提示未知 HTML 标记、组件引用爆红等问题处理

WebStorm 2024.3/IntelliJ IDEA 2024.3出现elementUI提示未知 HTML 标记、组件引用爆红等问题处理 1. 标题识别elementUI组件爆红 这个原因是&#xff1a; 在官网说明里&#xff0c;才版本2024.1开始&#xff0c;默认启用的 Vue Language Server&#xff0c;但是在 Vue 2 项目…...

机械设计学习资料

免费送大家学习资源&#xff0c;已整理好&#xff0c;仅供学习 下载网址&#xff1a; https://www.zzhlszk.com/?qZ02-%E6%9C%BA%E6%A2%B0%E8%AE%BE%E8%AE%A1%E8%A7%84%E8%8C%83SOP.zip...

Python 快速入门(上篇)❖ Python 字符串

Python 字符串 字符串格式化输出字符串拼接获取字符串长度字符串切片字符串处理方法 字符串格式化输出 name “xhx” age 30 # 方法1 print("我的名字是%s,今年%s岁了。 " % (name, age)) # 方法2 print(f"我的名字是{name},今年{age}岁了。")字符串拼接…...

Ubuntu中使用多版本的GCC

我的系统中已经安装了GCC11.4&#xff0c;在安装cuda时出现以下错误提示&#xff1a; 意思是当前的GCC版本过高&#xff0c;要在保留GCC11.4的同时安装GCC9并可以切换&#xff0c;可以通过以下步骤实现&#xff1a; 步骤 1: 安装 GCC 9 sudo apt-get update sudo apt-get ins…...

1+X应急响应(网络)文件包含漏洞:

常见网络攻击-文件包含漏洞&命令执行漏洞&#xff1a; 文件包含漏洞简介&#xff1a; 分析漏洞产生的原因&#xff1a; 四个函数&#xff1a; 产生漏洞的原因&#xff1a; 漏洞利用条件&#xff1a; 文件包含&#xff1a; 漏洞分类&#xff1a; 本地文件包含&#xff1a; …...

机器学习实战记录(1)

决策树——划分数据集 def splitDataSet(dataSet, axis, value): retDataSet [] #创建返回的数据集列表for featVec in dataSet: #遍历数据集if featVec[axis] value:reducedFeatVec featVec[:axis] #去掉axis特征reducedFeatVec.extend(featVec[axis1…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

【51单片机】4. 模块化编程与LCD1602Debug

1. 什么是模块化编程 传统编程会将所有函数放在main.c中&#xff0c;如果使用的模块多&#xff0c;一个文件内会有很多代码&#xff0c;不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里&#xff0c;在.h文件里提供外部可调用函数声明&#xff0c;其他.c文…...