图的拓扑排序算法

拓扑排序
什么是拓扑排序?
比如说,我们平时工作过程中一定听过一个词叫做—不能循环依赖。什么意思?
在这里插入图片描述
A依赖BCD,B依赖CD,C依赖D,D依赖EF,想要获得A的话,首先就要先有EF,有EF -> D -> C ->B -> A。整个这么一个编译的顺序就是拓扑排序。
所以说,拓扑排序就可以理解为是:根据先后顺序能够把工作依次做完,而且不缺依赖的顺序,就是拓扑序。
所以说为什么不能循环依赖,对于拓扑排序来说,一定是有向图并且无环
所以,如果依赖顺序是这样的话,那么就不叫拓扑序了。搞不定先做谁后做谁,互相依赖了。
在这里插入图片描述
练习
图结构如下所示,根据图结构,打印出它的拓扑序。
在这里插入图片描述
整体思路是这样:首先找到图中入度为0的(A,B),就是拓扑序中的头。将AB影响消掉,剩C ->D 再找入度为0的(C),再将C的影响消掉,最后剩D。不了解入度概念请看这篇帖子图的适配器。

代码实现
解释一下代码中各个变量。不了解Graph结构的还是请先看图的适配器。

public class Class03_TopologySort {public static List<Node> sortedTopology(Graph graph) {//inMap : 每个点所对应的入度信息//key:各个点的信息。//value: 点所对应的入度值。HashMap<Node, Integer> inMap = new HashMap<>();//如果入度值为0,则进队列中Queue<Node> zeroInQueue = new LinkedList<>();//遍历图中所有的nodesfor (Node node : graph.nodes.values()) {//填充inMapinMap.put(node, node.in);//如果此时入度值为0,直接放入队列中。if (node.in == 0) {zeroInQueue.add(node);}}//result存储的就是最终拓扑序后一个个打印出来的节点的顺序List<Node> result = new ArrayList<>();//如果队列不为nullwhile (!zeroInQueue.isEmpty()) {//弹出,并添加到List中Node cur = zeroInQueue.poll();result.add(cur);//遍历弹出的节点的nextsfor (Node next : cur.nexts) {//这一步就是将影响消除,将next节点的入度 - 1inMap.put(next, inMap.get(next) - 1);// - 1后如果为0,放入队列中等待遍历添加到resultif (inMap.get(next) == 0) {zeroInQueue.add(next);}}}return result;}
}

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

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

相关文章

webpack基础知识五:说说Loader和Plugin的区别?编写Loader,Plugin的思路?

一、区别 前面两节我们有提到Loader与Plugin对应的概念&#xff0c;先来回顾下 loader 是文件加载器&#xff0c;能够加载资源文件&#xff0c;并对这些文件进行一些处理&#xff0c;诸如编译、压缩等&#xff0c;最终一起打包到指定的文件中plugin 赋予了 webpack 各种灵活的…

二分法的应用

文章目录 什么是二分法&#x1f3ae;二分查找的优先级二分查找的步骤&#x1f4a5;图解演示&#x1f9e9; 代码演示&#x1fad5;python程序实现&#x1f408;‍⬛C程序实现&#x1f415;‍&#x1f9ba;C程序实现&#x1f42f;Java程序实现&#x1f433; 非常规类二分查找&…

电源控制--条件稳定

控制系统的条件稳定是指系统在一定条件下能够保持稳定性的特性。稳定性是控制系统设计中非常重要的概念&#xff0c;它涉及系统的输出在时间上是否趋向于有限值或者周期性变化&#xff0c;而不是无限增长或发散。 在控制系统中&#xff0c;条件稳定的要求通常涉及到以下几个方…

Sentieon|应用教程:利用Sentieon Python API引擎为自研算法加速

背景 Sentieon套装中所有模块的速度都远超对应开源软件的数倍至数十倍&#xff0c;用户在使用这些模块的同时&#xff0c;有时也希望Sentieon团队可以帮助加速自己开发的定制化软件。为了帮助这些用户能在自研软件上享受到Sentieon模块的速度&#xff0c;我们开发了Python API…

【深度学习MOT】SMILEtrack SiMIlarity LEarning for Multiple Object Tracking,论文

论文&#xff1a;https://arxiv.org/abs/2211.08824 文章目录 AbstractIntroduction2. 相关工作2.1 基于检测的跟踪2.1.1 检测方法2.1.2 数据关联方法 2.2 基于注意力的跟踪 3. 方法3.1 架构概述3.2 用于重新识别的相似性学习模块&#xff08;SLM&#xff09; Experimental Res…

【Python机器学习】实验08 决策树

文章目录 决策树1 创建数据2 定义香农信息熵3 条件熵4 信息增益5 计算所有特征的信息增益&#xff0c;选择最优最大信息增益的特征返回6 利用ID3算法生成决策树7 利用数据构造一颗决策树Scikit-learn实例决策树分类决策树回归Scikit-learn 的决策树参数决策树调参 实验1 通过sk…

【C++】string的使用

1、string的使用 #define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include<string> using namespace std;void Test1() {string s1;string s2("hello");cin >> s1;cout << s1 << endl;//strcat【字符串拼接】string ret1 s…

【solon生态】- solon.cloud.micrometer插件使用指南及micrometer详解

solon.cloud.micrometer插件使用指南 solon是什么solon的cloud生态图快速入门 micrometer指南micrometer是什么监控系统 Supported Monitoring Systems注册表 Registry度量 Meters度量名 Naming Meters度量标签 Tag Naming通用标签 Common Tags 指标过滤器 MeterFilter聚合速率…

月报总结|Moonbeam 7月份大事一览

炎炎夏日&#xff0c;Moonbeam于越南举办了线下交流会&#xff0c;在EthCC 2023和以太坊社区成员共同讨论多链应用&#xff0c;在Polkadot Decoded中分享了Moonbeam的与众不同之处。 Bear Necessities Hackathon也于本月圆满结束&#xff0c;选出了每个赛道最杰出的项目&#…

JS逆向系列之猿人学爬虫第8题-验证码-图文点选

题目地址 https://match.yuanrenxue.cn/match/8本题的难点就在于验证码的识别,没啥js加密,只要识别对了携带坐标就给返回数据 回过头来看验证码 这里复杂的字体比较多,人看起来都有点费劲(感觉可能对红绿色盲朋友不太又好)&#x

redis原理 1:鞭辟入里 —— 线程 IO 模型

Redis 是个单线程程序&#xff01;这点必须铭记。 也许你会怀疑高并发的 Redis 中间件怎么可能是单线程。很抱歉&#xff0c;它就是单线程&#xff0c;你的怀疑暴露了你基础知识的不足。莫要瞧不起单线程&#xff0c;除了 Redis 之外&#xff0c;Node.js 也是单线程&#xff0c…

iPhone手机怎么恢复出厂设置(详解)

如果您的iPhone遇到了手机卡顿、软件崩溃、内存不足或者忘记手机解锁密码等问题&#xff0c;恢复出厂设置似乎是万能的解决方法。 什么是恢复出厂设置&#xff1f;简单来说&#xff0c;就是让手机重新变成一张白纸&#xff0c;将手机所有数据都进行格式化&#xff0c;只保留原…

C++结构体部分显式构造导致编译异常分析

今天调试了一段代码如下 #include <iostream> #include <shared_mutex>#define SECT_NUM 2 #define DI_HIGH_PERM 2 #define DI_READ 1 #define DI_WRITE 2 #define FMT_BIN 1#define USER_PATH "d:\\fafiles\\dbtest\\"typedef unsigned long DW…

Python 之禅

Python 社区的理念都包含在 Tim Peters 撰写的 “Python 之禅” 中 在 Windows 平台的 cmd 命令中打开 python&#xff0c;输入 import this&#xff0c;就能看到 Python 之禅: 翻译&#xff1a; Tim Peters 的 python 之禅Beautiful is better than ugly. # 优美胜于丑陋&am…

鸿鹄工程项目管理系统em Spring Cloud+Spring Boot+前后端分离构建工程项目管理系统em

​ Java版工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离 功能清单如下&#xff1a; 首页 工作台&#xff1a;待办工作、消息通知、预警信息&#xff0c;点击可进入相应的列表 项目进度图表&#xff1a;选择&#xff08;总体或单个&#xff09;项目…

chapter13:springboot与任务

Spring Boot与任务视频 1. 异步任务 使用注解 Async 开启一个异步线程任务&#xff0c; 需要在主启动类上添加注解EnableAsync开启异步配置&#xff1b; Service public class AsyncService {Asyncpublic void hello() {try {Thread.sleep(3000);} catch (InterruptedExcept…

vue3 动态导入src/page目录下的所有子文件,并自动注册所有页面组件

main.js添加一下代码&#xff1a; const importAll (modules) > {Object.keys(modules).forEach((key) > {const component key.replace(/src/, /).replace(.vue, );const componentName key.split(/).slice(-2, -1)[0] -page;app.component(componentName, modules…

Asynq: 基于Redis实现的Go生态分布式任务队列和异步处理库

Asynq[1]是一个Go实现的分布式任务队列和异步处理库&#xff0c;基于redis&#xff0c;类似Ruby的sidekiq[2]和Python的celery[3]。Go生态类似的还有machinery[4]和goworker 同时提供一个WebUI asynqmon[5]&#xff0c;可以源码形式安装或使用Docker image, 还可以和Prometheus…

网络基本概念

目录 一、IP地址 1. 概念 2. 格式 3. 特殊IP 二、端口号 1.概念 2. 格式 3.注意事项 三、 协议 1. 概念 2. 作用 四、协议分层 1. 网络设备所在分层 五、封装与分用 六、客户端和服务器 1. 客户端与服务器通信的过程 一、IP地址 1. 概念 IP地址主要用于标识网络主机.其他网络…

如何搭建个人的GPT网页服务

写在前面 在创建个人的 GPT网页之前&#xff0c;我登录了 Git 并尝试了一些开源项目&#xff0c;但是没有找到满足我个性化需求的设计。虽然许多收费的 GPT网页提供了一些免费额度&#xff0c;足够我使用&#xff0c;但是公司的安全策略会屏蔽这些网页。因此&#xff0c;我决定…