算法系列--BFS解决拓扑排序

💕"请努力活下去"💕
作者:Lvzi
文章主要内容:算法系列–算法系列–BFS解决拓扑排序
在这里插入图片描述

大家好,今天为大家带来的是算法系列--BFS解决拓扑排序

前言:什么是拓扑排序
拓扑排序–解决有顺序的排序问题(要做事情的先后顺序)
在这里插入图片描述
几个基本概念

  1. 有向无环图:有方向,但是不存在环路
  2. 入度:有多少条路可以走到当前节点
  3. 出度:从当前节点出发,有多少条线路

拓扑排序问题的思路比较固定,难点在于灵活的采用不同的容器去建图和表示每个节点的入度信息,下面是拓扑排序问题的步骤:

Step1:建图

建立一个有向图来表示做事情的先后顺序

如何建图–灵活使用语言提供的容器

要存储的是:一个节点与其所相连的节点(边),两点构成一条线段
建立映射关系:
–哈希表存储
Map<Point,List< Point >>

表示每一个节点的入度:
我们是根据入度是否为0来决定先后顺序的

一个节点的入度就是有多少个指向该节点的边

使用数组int[] in表示

在这里插入图片描述

Step2.进行拓扑排序(队列 + bfs)

  1. 将所有入度为0的节点添加进队列
    在这里插入图片描述

  2. 循环队列

    • 获取头结点t,将t添加进入最后的结果之中(如果要表示的话)
    • 将与t相连的边删除–等价于将与t相连的点的入度减1
    • 判断与t相连的点的入度是否为0,如果为0,表示是新的起点,添加进队列之中
  3. 直到图中没有节点或者没有入度为0的节点(有环)
    在这里插入图片描述

注意有环的情况
在这里插入图片描述

一.课程表

题目链接:课程表
在这里插入图片描述

分析:

拓扑排序

  • 如果最后存在入度不为0的点–证明有环–无法按照p数组的顺序完成课程
  • 全为0,证明可以完成所有课程

代码:

class Solution {// 本题节点就是所有的可成public boolean canFinish(int n, int[][] p) {// 1.建图Map<Integer,List<Integer>> edges = new HashMap<>();int[] in = new int[n];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]++;// 入度加1}// 2.拓扑排序Queue<Integer> q = new LinkedList<>();for(int i = 0; i < n; i++)// 将所有入度为0的点添加进入队列if(in[i] == 0)q.add(i);// bfs// 得到对头元素 -- 删除与其相连的边 -- 找到下一个起始位置while(!q.isEmpty()) {int t = q.poll();for(int i : edges.getOrDefault(t,new ArrayList<>())) {// 将与t相连的点的入度减1in[i]--;if(in[i] == 0) q.add(i);// 如果入度为0,表示新的起点,添加进队列}}// 判断是否存在入度不为0 的点,如果存在,证明有环,则无法完成所有课程,返回falsefor(int i : in)if(i != 0) return false;return true;}
}

总结:

  1. 注意本题p数组的指向,是b指向a
  2. 大致的过程很简单
    • 建图:建立点与点之间的联系(Map),统计所有点的入度情况–循环遍历即可
    • 拓扑排序:先将所有入度为0的点添加进入队列(起点),bfs循环遍历
  3. 一定要注意我们建的图可能有环,也可能无环,如果有环,最后图中一定有入度不为0的节点

二.课程表II

题目链接:课程表II
在这里插入图片描述

分析:

和上一道题目相同 只需记录排序结果即可

代码:

import java.util.Collections;
class Solution {public int[] findOrder(int n, int[][] p) {// 1.建图Map<Integer,List<Integer>> edges = new HashMap<>();int[] in = new int[n];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]++;// 入度加1}// 2.拓扑排序Queue<Integer> q = new LinkedList<>();for(int i = 0; i < n; i++)// 将所有入度为0的点添加进入队列if(in[i] == 0)q.add(i);int[] ret = new int[n];int index = 0;// bfswhile(!q.isEmpty()) {int t = q.poll();ret[index++] = t;for(int i : edges.getOrDefault(t,new ArrayList<>())) {// 将与t相连的点的入度减1in[i]--;if(in[i] == 0) q.add(i);// 如果入度为0,表示新的起点,添加进队列}}return index == n ? ret : new int[]{};}
}

三.⽕星词典

题目链接:⽕星词典
在这里插入图片描述

分析:

这里面的节点就是一个一个字符,题目最终要求的是字符的先后顺序–拓扑排序
三步:建图,拓扑排序,判断

在这里插入图片描述

代码:

class Solution {Map<Character,List<Character>> edges = new HashMap<>();// 建图使用Map<Character,Integer> in = new HashMap<>();// 统计每一个节点的入度信息public String alienOrder(String[] words) {// 初始化入度信息for(String str : words)for(int i = 0; i < str.length(); i++)in.put(str.charAt(i),0);// 建图  使用两层for循环来搜集信息int n = words.length;for(int i = 0; i < n - 1; i++) {for(int j = i + 1; j < n; j++) {String s1 = words[i], s2 = words[j];int len = Math.min(s1.length(),s2.length()), index = 0;while(index < len && s1.charAt(index) == s2.charAt(index))index++;// 处理不合法的情况  s1 = abc  s2 = abif(index == s2.length() && index < s1.length()) return "";// 走到两个字符串不相同的字母if(index >= len) continue;// 防止越界char prev = s1.charAt(index), behind = s2.charAt(index);if(!edges.containsKey(prev))edges.put(prev,new ArrayList<>());if(!edges.get(prev).contains(behind)) {// 这里不加if判断也行,加了是为了减少冗余信息的加入edges.get(prev).add(behind);in.put(behind,in.get(behind) + 1);}}}// 2.拓扑排序StringBuffer ret = new StringBuffer();Queue<Character> q = new LinkedList<>();for(char ch : in.keySet()) // 将度为0的节点添加进队列之中if(in.get(ch) == 0) q.add(ch);while(!q.isEmpty()) {char t = q.poll();ret.append(t);// 遍历相连的点for(char ch : edges.getOrDefault(t,new ArrayList<>())) {in.put(ch,in.get(ch) - 1);if(in.get(ch) == 0) q.add(ch);}}// 判断是否存在入度不为0的点for(char ch : in.keySet()) if(in.get(ch) != 0) return "";return ret.toString();}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/318088.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

docker各目录含义

目录含义builder构建docker镜像的工具或过程buildkit用于构建和打包容器镜像&#xff0c;官方构建引擎&#xff0c;支持多阶段构建、缓存管理、并行化构建和多平台构建等功能containerd负责容器生命周期管理&#xff0c;能起、停、重启&#xff0c;确保容器运行。负责镜管理&am…

Java设计模式 _结构型模式_组合模式

一、组合模式 1、组合模式 组合模式&#xff08;Composite Pattern&#xff09;是这一种结构型设计模式。又叫部分整体模式。组合模式依据树形结构来组合对象&#xff0c;用来表示部分以及整体层次关系。即&#xff1a;创建了一个包含自己对象组的类&#xff0c;该类提供了修改…

Idea报错:无法访问org.springframework.boot.SpringApplication

在开发项目时&#xff0c;常常会遇到这种问题&#xff0c;报错信息如下图所示 版本号与jdk版本号存在对应关系&#xff0c;61.0对应jdk17&#xff0c;52.0对应jdk8 所以是某个依赖的版本太高&#xff0c;降低该依赖的版本即可 具体步骤&#xff1a; ①修改pom.xml中spring b…

ASP.NET实验室预约系统的设计

摘 要 实验室预约系统的设计主要是基于B/S模型&#xff0c;在Windows系统下&#xff0c;运用ASP.NET平台和SQLServer2000数据库实现实验室预约功能。该设计主要实现了实验室的预约和管理功能。预约功能包括老师对实验室信息、实验项目和实验预约情况的查询以及对实验室的预约…

ubuntu系统搭建pytorch环境详细步骤【笔记】

实践设备&#xff1a;华硕FX-PRO&#xff08;NVIDIA GeForce GTX 960M&#xff09; 搭建PyTorch环境的详细步骤如下&#xff1a; 1.安装Ubuntu系统&#xff1a; 下载Ubuntu的镜像文件并制作启动盘。将启动盘插入计算机&#xff0c;启动计算机并按照提示安装Ubuntu系统。 2.…

Linux内核之原子操作:atomic_long_dec用法实例(六十七)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

一起Talk Android吧(第五百五十八回:lombok用法)

文章目录 1. 概述2. 使用方法3. 内容总结 各位看官们大家好&#xff0c;上一回中介绍了如何获取文件读写权限的知识,本章回中将介绍lombok相关的知识。闲话休提&#xff0c;言归正转&#xff0c;让我们一起Talk Android吧&#xff01; 1. 概述 这是一个java库&#xff0c;用来…

ES全文检索支持拼音和繁简检索

ES全文检索支持拼音和繁简检索 1. 实现目标2. 引入pinyin插件2.1 编译 elasticsearch-analysis-pinyin 插件2.2 安装拼音插件 3. 引入ik分词器插件3.1 已有作者编译后的包文件3.2 只有源代码的版本3.3 安装ik分词插件 4. 建立es索引5.测试检索6. 繁简转换 1. 实现目标 ES检索时…

flutter开发实战-build apk名称及指令abiFilters常用gradle设置

flutter开发实战-build apk名称及指令abiFilters常用gradle设置 最近通过打包flutter build apk lib/main.dart --release&#xff0c;发现apk命名规则需要在build.gradle设置。这里记录一下。 一、apk命名规则 在android/app/build.gradle中需要设置 android.applicationVa…

Pandas入门篇(二)-------Dataframe篇4(进阶)(Dataframe的进阶用法)(机器学习前置技术栈)

目录 概述一、复合索引&#xff08;一&#xff09;创建具有复合索引的 DataFrame1. 使用 set_index 方法&#xff1a;2.在创建 DataFrame 时直接指定索引&#xff1a; &#xff08;二&#xff09;使用复合索引进行数据选择和切片&#xff08;三&#xff09;重置索引&#xff08…

rabbitMq 0 到1

前言 工作中MQ的使用场景是数不胜数&#xff0c;每个公司的技术选型又不太一样&#xff0c;用的哪个MQ&#xff0c;我们必须要先玩起来&#xff0c;RabbitMQ在windows安装遇到很多问题&#xff0c;博客也是五花八门&#xff0c;算了还是自己搞吧&#xff0c;记录一下&#xff…

五大开放式耳机推荐,选对耳机让运动更带感!

看似精彩的户外运动经历背后&#xff0c;其实是枯燥的体能运动和训练&#xff0c;以及独自长途和长时间旅行伴随的孤独感&#xff0c;而排解这些不良情绪的最佳方式就是音乐。如果你希望在运动、舒适、安全和音质之间获得一个最佳平衡&#xff0c;那相比入耳式耳机&#xff0c;…

护航智慧交通安全 | 聚铭精彩亮相2024交通科技创新及信创产品推广交流会

4月26日&#xff0c;石家庄希尔顿酒店内&#xff0c;河北省智能交通协会盛大举办2024年度交通科技创新及信创产品推广交流会。聚铭网络受邀参与&#xff0c;携旗下安全产品及解决方案精彩亮相&#xff0c;为智慧交通安全保驾护航。 为深化高速公路创新驱动发展战略&#xff0…

pthread线程相关

LWP :轻量级 进程&#xff0c;本质仍是进程 进程 &#xff1a;独立地址空间&#xff0c;拥有PCB 线程&#xff1a;有独立的TCB&#xff0c;但没有独立的地址空间&#xff08;共享&#xff09; 区别 &#xff1a;在与是否共享地址文件 进程 &#xff08;独居&#xff09;&am…

10分钟了解数据质量管理-奥斯汀格里芬 Apache Griffin

在不重视数据质量的大数据发展时期&#xff0c;Griffin并不能引起重视&#xff0c;但是随着数据治理在很多企业的全面开展与落地&#xff0c;数据质量的问题开始引起重视。 1.Griffin简介 Griffin是一个开源的大数据数据质量解决方案&#xff0c;由eBay开源&#xff0c;它支持…

模型智能体开发之metagpt-单智能体实践

需求分析 根据诉求完成函数代码的编写&#xff0c;并实现测试case&#xff0c;输出代码 代码实现 定义写代码的action action是动作的逻辑抽象&#xff0c;通过将预设的prompt传入llm&#xff0c;来获取输出&#xff0c;并对输出进行格式化 具体的实现如下 定义prompt模版 …

IDEA 开发找到 java-web 发布到 tomcat 的路径

使用 IDEA 开发 java web 应用&#xff0c;有没有遇到需要找到 tomcat 路径的问题 为什么要找 tomcat 路径呢&#xff1f; 拿我的项目来举例&#xff0c;有统一的线上线下 logback.xml 配置&#xff0c;配置时业务、框架日志输出到 file&#xff0c;少量的启动日志输出到 con…

黑马点评项目个人笔记+项目优化调整

博客须知 本篇博客内容来源与黑马点评项目实战篇-16.用户签到-实现签到功能_哔哩哔哩_bilibili&#xff0c;作者对视频内容进行了整合&#xff0c;由于记笔记时图片使用的是本地路径&#xff0c;所以导致博客的图片无法正常显示&#xff0c;如果有图片需求可以下载上方的pdf须…

【SQL每日一练】统计复旦用户8月练题情况

文章目录 题目一、分析二、题解1.使用case...when..then2.使用if 题目 现在运营想要了解复旦大学的每个用户在8月份练习的总题目数和回答正确的题目数情况&#xff0c;请取出相应明细数据&#xff0c;对于在8月份没有练习过的用户&#xff0c;答题数结果返回0. 示例代码&am…

一加Ace3/12/Ace2pro手机ColorOS14刷KernelSU内核ROOT-解决无限重启变砖

一加Ace3/一加12/一加11等手机升级了安卓14底层&#xff0c;并且ColorOS版本也更新到了14版本界面和功能都比之前的系统表现更加优秀&#xff0c;但刷机方面&#xff0c;相对之前存在一些差异&#xff0c;特别是KernelSU内核级别root权限&#xff0c;不再支持一键刷入KernelSU通…