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

图论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 调用无向图的深度优先后续遍历方法&#xff0c;进行DFS 1 拓扑排序 对一个有向无环图G进行拓扑排序&#xff0c;是将…...

SecureCRT 9.4.2最新终端SSH工具

SecureCRT是一款终端SSH工具&#xff0c;它提供了类似于Telnet和SSH等协议的远程访问功能。SecureCRT软件特色包括&#xff1a; 支持SSH&#xff08;SSH1和SSH2&#xff09;的终端仿真程序&#xff0c;能在Windows下登录UNIX或Linux服务器主机。SecureCRT支持SSH&#xff0c;同…...

基于python+django的美食餐厅点餐订餐网站

运行环境 开发语言&#xff1a;Python python框架&#xff1a;django 软件版本&#xff1a;python3.7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;PyCharm/vscode 前端框架:vue.js 项目介绍 本论文主要论述了如何使用python语言开发…...

Moka人事:实现无代码开发的API连接,打通电商平台与用户运营系统

无代码开发的API连接&#xff1a;Moka人事的核心优势 Moka人事&#xff0c;是北京希瑞亚斯科技有限公司于2015年推出的一款数据驱动的智能化HR SaaS产品。这款产品的主要优势在于其无需进行API开发即可实现系统的连接和集成&#xff0c;这不仅大大提升了企业的工作效率&#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下功能完善的报表平台&#xff0c;它附带了易于使用的Visual Studio报表设计器和丰富的报表控件集&#xff0c;包括数据透视表、图表&#xff0c;因此您可以构建无与伦比、信息清晰的报表 界面组件DevExpress Reporting v23.1已经发布一段…...

电容容量换算电池容量,以及RTC持续时间计算

依据 公式1&#xff1a;QI*t 公式2&#xff1a;QC*U 其中&#xff1a; Q&#xff1a; 电荷量 &#xff08;库仑&#xff09; I&#xff1a; 电流 &#xff08;安培&#xff09; t&#xff1a; 时间 &#xff08;秒&#xff09; C&#xff1a; 电容量 &#xff08;法拉&#xf…...

【BIM入门实战】高程点无法放置的解决方法

文章目录 一、问题提出二、解决办法1. 检查模型图形样式2. 高程点可以放置的图元一、问题提出 在平面图中添加高程点时有时会遇到无法在楼板等平面构件上放置高程点,应如何设置才能使高程点正常放置? 如下图所示,楼板上无法放置高程点: 二、解决办法 1. 检查模型图形样式…...

CRM系统对科技企业有哪些帮助

随着国家政策的倾斜和5G等相关基础技术的发展&#xff0c;中国人工智能产业在各方的共同推动下进入爆发式增长阶段&#xff0c;市场发展潜力巨大。CRM客户管理系统作为当下最热门的企业应用&#xff0c;同样市场前景广阔。那么&#xff0c;CRM系统对科技企业有哪些帮助&#xf…...

用excel计算一个矩阵的转置矩阵

假设我们的原矩阵是一个3*3的矩阵&#xff1a; 125346789 现在求它的转置矩阵&#xff1a; 鼠标点到一个空白的地方&#xff0c;用来存放结果&#xff1a; 插入-》函数&#xff1a; 选择TRANSPOSE&#xff0c;这个就是求转置矩阵的函数&#xff1a; 点击“继续”&#xff1a…...

WPF 中的 ControlTemplate 和 DataTemplate 有什么区别

在WPF中&#xff0c;ControlTemplate和DataTemplate都是模板&#xff0c;它们都可以用来定义一段可重复使用的XAML标记。然而&#xff0c;它们的用途和应用场景有很大的不同。 ControlTemplate&#xff1a; ControlTemplate是用来定义控件的外观和视觉行为的。每个WPF控件都有…...

3D重建相关

目录 <font colorblue>整个3D重建的过程是怎样的<font colorblue>体素、网格、点云之间的关系是什么<font colorblue>点云中的颜色怎么处理成最终3D模型上的颜色<font colorblue>点云还原的3D模型的颜色怎么处理&#xff0c;点云有颜色数据&#xff1f…...

字符串数组排序(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)); }降序排 降序排&#xff0c;可传入第二个…...

调用电商集成平台 聚水潭 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:探索所有权和借用机制

大家好&#xff01;我是lincyang。 今天&#xff0c;我们将一起深入探索Rust语言中的一个核心概念&#xff1a;所有权和借用机制。 这些特性是Rust区别于其他语言的重要特点&#xff0c;它们在内存管理和并发编程中扮演着关键角色。 一、Rust所有权机制 1. 什么是所有权&#x…...

Python之冒泡排序(AI自动写文章项目测试)

全自动AI生成文章测试&#xff0c;如有不合理地方&#xff0c;请见谅。 一、冒泡排序简介 1.1 冒泡排序概述 冒泡排序&#xff08;Bubble Sort&#xff09;是一种简单的排序算法&#xff0c;通过不断交换相邻元素的位置&#xff0c;将最大&#xff08;或最小&#xff09;的元…...

spring cloud微服务中多线程下,子线程通过feign调用其它服务,请求头token等丢失

在线程池中&#xff0c;子线程调用其他服务&#xff0c;请求头丢失&#xff0c;token为空的情况 看了很多篇文章的处理方法和在自己亲测的情况下做出说明&#xff1a; 第一种&#xff1a; 这种方式只支持在主线程情况下&#xff0c;能够处理&#xff0c;在多线程情况下&#…...

Nacos 高级玩法:深入探讨分布式配置和服务发现

&#x1f38f;&#xff1a;你只管努力&#xff0c;剩下的交给时间 &#x1f3e0; &#xff1a;小破站 Nacos 高级玩法&#xff1a;深入探讨分布式配置和服务发现 前言第一&#xff1a;nacos高级配置管理1. 动态配置的基本使用&#xff1a;2. 监听策略的原理和实现&#xff1a;3…...

CCF CSP认证历年题目自练Day45

这几天搞泰迪杯数据分析技能赛去了。等拿国奖了就出一期关于泰迪杯的。 题目 试题编号&#xff1a; 201703-3 试题名称&#xff1a; Markdown 时间限制&#xff1a; 1.0s 内存限制&#xff1a; 256.0MB 问题描述&#xff1a; 问题描述   Markdown 是一种很流行的轻量级标记…...

outlook群发邮件

一米群发软件使用Outlook进行群发邮件的步骤如下&#xff1a; 打开Outlook软件&#xff0c;点击页面上方的“新建电子邮件”选项。在弹出的新邮件中&#xff0c;输入收件人和邮件主题&#xff0c;在收件人输入框中输入多个需要接收邮件的邮箱地址&#xff0c;用分号&#xff0…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...