图论16-拓扑排序
文章目录
- 1 拓扑排序
- 2 拓扑排序的普通实现
- 2.1 算法实现 - 度数为0入队列
- 2.2 拓扑排序中的环检测
- 3 深度优先遍历的后续遍历
- 3.1 使用环检测类先判断是否有环
- 3.2 调用无向图的深度优先后续遍历方法,进行DFS
1 拓扑排序
-
对一个有向无环图G进行拓扑排序,是将G中所有顶点排成一个
线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。 -
通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称
拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
2 拓扑排序的普通实现


2.1 算法实现 - 度数为0入队列
Queue<Integer> q = new LinkedList<>();for(int v = 0; v < G.V(); v ++){indegrees[v] = G.indegree(v);//入度度数为0的入队,找源点if(indegrees[v] == 0) q.add(v);
}while(!q.isEmpty()){ // 如果有环,那么环上的点从入口开始就无法进入队列int cur = q.remove();//相邻的顶点入队res.add(cur);//相邻的顶点入度都减1for(int next: G.adj(cur)){indegrees[next] --;// 入度为0的直接入队if(indegrees[next] == 0) q.add(next);}
}
2.2 拓扑排序中的环检测
能够进行拓扑排序的图是没有环的,否则无法进行拓扑排序。
在拓扑排序的实现过程中,如果返回的res数组中的点的数量与图的点的数量不一致,则说明有环。因为环上的点由于度数无法为0,无法进入队列,从而进入res数组返回答案。

if(res.size() != G.V()){hasCycle = true;res.clear();
}
3 深度优先遍历的后续遍历

- 根节点最后遍历,讲得到的序列反过来,就是拓扑排序,但是这种方法无法实现环检测。

3.1 使用环检测类先判断是否有环
private boolean hasCycle = false;hasCycle = (new DirectedCycleDetection(G)).hasCycle();if(hasCycle) return;
3.2 调用无向图的深度优先后续遍历方法,进行DFS
GraphDFS dfs = new GraphDFS(G);for(int v: dfs.post())res.add(v);
相关文章:
图论16-拓扑排序
文章目录 1 拓扑排序2 拓扑排序的普通实现2.1 算法实现 - 度数为0入队列2.2 拓扑排序中的环检测 3 深度优先遍历的后续遍历3.1 使用环检测类先判断是否有环3.2 调用无向图的深度优先后续遍历方法,进行DFS 1 拓扑排序 对一个有向无环图G进行拓扑排序,是将…...
SecureCRT 9.4.2最新终端SSH工具
SecureCRT是一款终端SSH工具,它提供了类似于Telnet和SSH等协议的远程访问功能。SecureCRT软件特色包括: 支持SSH(SSH1和SSH2)的终端仿真程序,能在Windows下登录UNIX或Linux服务器主机。SecureCRT支持SSH,同…...
基于python+django的美食餐厅点餐订餐网站
运行环境 开发语言:Python python框架:django 软件版本:python3.7 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:PyCharm/vscode 前端框架:vue.js 项目介绍 本论文主要论述了如何使用python语言开发…...
Moka人事:实现无代码开发的API连接,打通电商平台与用户运营系统
无代码开发的API连接:Moka人事的核心优势 Moka人事,是北京希瑞亚斯科技有限公司于2015年推出的一款数据驱动的智能化HR SaaS产品。这款产品的主要优势在于其无需进行API开发即可实现系统的连接和集成,这不仅大大提升了企业的工作效率&#x…...
【Spring】超详细讲解AOP(面向切面编程)
文章目录 1. 前言2. 什么是AOP3. AOP快速入门4. AOP的核心概念5. 切点表达式6. 切点函数7. 通知8. 总结 1. 前言 本文围绕AOP进行讲解,AOP可以做什么,涉及到了哪些注解,以及各个注解运行的时机,以及Around相较于其它注解有什么不同,并且如果要执行目标方法需要怎么做 2. 什么…...
界面组件DevExpress Reporting v23.1亮点 - 全新升级报表查看器
DevExpress Reporting是.NET Framework下功能完善的报表平台,它附带了易于使用的Visual Studio报表设计器和丰富的报表控件集,包括数据透视表、图表,因此您可以构建无与伦比、信息清晰的报表 界面组件DevExpress Reporting v23.1已经发布一段…...
电容容量换算电池容量,以及RTC持续时间计算
依据 公式1:QI*t 公式2:QC*U 其中: Q: 电荷量 (库仑) I: 电流 (安培) t: 时间 (秒) C: 电容量 (法拉…...
【BIM入门实战】高程点无法放置的解决方法
文章目录 一、问题提出二、解决办法1. 检查模型图形样式2. 高程点可以放置的图元一、问题提出 在平面图中添加高程点时有时会遇到无法在楼板等平面构件上放置高程点,应如何设置才能使高程点正常放置? 如下图所示,楼板上无法放置高程点: 二、解决办法 1. 检查模型图形样式…...
CRM系统对科技企业有哪些帮助
随着国家政策的倾斜和5G等相关基础技术的发展,中国人工智能产业在各方的共同推动下进入爆发式增长阶段,市场发展潜力巨大。CRM客户管理系统作为当下最热门的企业应用,同样市场前景广阔。那么,CRM系统对科技企业有哪些帮助…...
用excel计算一个矩阵的转置矩阵
假设我们的原矩阵是一个3*3的矩阵: 125346789 现在求它的转置矩阵: 鼠标点到一个空白的地方,用来存放结果: 插入-》函数: 选择TRANSPOSE,这个就是求转置矩阵的函数: 点击“继续”:…...
WPF 中的 ControlTemplate 和 DataTemplate 有什么区别
在WPF中,ControlTemplate和DataTemplate都是模板,它们都可以用来定义一段可重复使用的XAML标记。然而,它们的用途和应用场景有很大的不同。 ControlTemplate: ControlTemplate是用来定义控件的外观和视觉行为的。每个WPF控件都有…...
3D重建相关
目录 <font colorblue>整个3D重建的过程是怎样的<font colorblue>体素、网格、点云之间的关系是什么<font colorblue>点云中的颜色怎么处理成最终3D模型上的颜色<font colorblue>点云还原的3D模型的颜色怎么处理,点云有颜色数据?…...
字符串数组排序(Java/JavaScript代码版)
Java public static void main(String[] args) throws Exception {String[] arr new String[] {"abc","xyz","efg"};// 默认按自然升序排Arrays.sort(arr);System.out.println(Arrays.toString(arr)); }降序排 降序排,可传入第二个…...
调用电商集成平台 聚水潭 api接口示例
先上工具类 package com.zuodou.utlis;import org.springframework.beans.factory.annotation.Value; import org.springframework.stereotype.Component;import javax.xml.crypto.Data; import java.io.*; import java.net.HttpURLConnection; import java.net.URL; import j…...
深入Rust:探索所有权和借用机制
大家好!我是lincyang。 今天,我们将一起深入探索Rust语言中的一个核心概念:所有权和借用机制。 这些特性是Rust区别于其他语言的重要特点,它们在内存管理和并发编程中扮演着关键角色。 一、Rust所有权机制 1. 什么是所有权&#x…...
Python之冒泡排序(AI自动写文章项目测试)
全自动AI生成文章测试,如有不合理地方,请见谅。 一、冒泡排序简介 1.1 冒泡排序概述 冒泡排序(Bubble Sort)是一种简单的排序算法,通过不断交换相邻元素的位置,将最大(或最小)的元…...
spring cloud微服务中多线程下,子线程通过feign调用其它服务,请求头token等丢失
在线程池中,子线程调用其他服务,请求头丢失,token为空的情况 看了很多篇文章的处理方法和在自己亲测的情况下做出说明: 第一种: 这种方式只支持在主线程情况下,能够处理,在多线程情况下&#…...
Nacos 高级玩法:深入探讨分布式配置和服务发现
🎏:你只管努力,剩下的交给时间 🏠 :小破站 Nacos 高级玩法:深入探讨分布式配置和服务发现 前言第一:nacos高级配置管理1. 动态配置的基本使用:2. 监听策略的原理和实现:3…...
CCF CSP认证历年题目自练Day45
这几天搞泰迪杯数据分析技能赛去了。等拿国奖了就出一期关于泰迪杯的。 题目 试题编号: 201703-3 试题名称: Markdown 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述 Markdown 是一种很流行的轻量级标记…...
outlook群发邮件
一米群发软件使用Outlook进行群发邮件的步骤如下: 打开Outlook软件,点击页面上方的“新建电子邮件”选项。在弹出的新邮件中,输入收件人和邮件主题,在收件人输入框中输入多个需要接收邮件的邮箱地址,用分号࿰…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
