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

Java数据结构与算法(有向无环图)

前言

有向无环图(Directed Graph)是在有向图的基础上,增加无环的检查。

实现原理

使用邻接表表示法实现有向图相对简单明了,步骤也相对简单。

1:首先创建有向图

2.创建顶点

3.顶点间创建边

4.创建边的过程中检查节点是否存在环,每个节点的检查采用递归。

具体代码实现

package test13;import java.util.*;public class DAG {private Map<Vertex, List<Vertex>> adjacencyList;public DAG() {this.adjacencyList = new HashMap<>();}// 添加顶点public void addVertex(String label) {adjacencyList.putIfAbsent(new Vertex(label), new ArrayList<>());}// 添加边并检查是否会形成环public boolean addEdge(String sourceLabel, String destinationLabel) {Vertex source = new Vertex(sourceLabel);Vertex destination = new Vertex(destinationLabel);if (!adjacencyList.containsKey(source) || !adjacencyList.containsKey(destination)) {throw new IllegalArgumentException("顶点不存在");}adjacencyList.get(source).add(destination);// 检查是否形成环if (hasCycle()) {adjacencyList.get(source).remove(destination);return false;}return true;}// 深度优先搜索检查环private boolean hasCycle() {Set<Vertex> visited = new HashSet<>();Set<Vertex> recursionStack = new HashSet<>();for (Vertex vertex : adjacencyList.keySet()) {if (hasCycleUtil(vertex, visited, recursionStack)) {return true;}}return false;}private boolean hasCycleUtil(Vertex vertex, Set<Vertex> visited, Set<Vertex> recursionStack) {if (recursionStack.contains(vertex)) {return true;}if (visited.contains(vertex)) {return false;}visited.add(vertex);recursionStack.add(vertex);for (Vertex neighbor : adjacencyList.get(vertex)) {if (hasCycleUtil(neighbor, visited, recursionStack)) {return true;}}recursionStack.remove(vertex);return false;}// 拓扑排序public List<Vertex> topologicalSort() {Set<Vertex> visited = new HashSet<>();Stack<Vertex> stack = new Stack<>();for (Vertex vertex : adjacencyList.keySet()) {if (!visited.contains(vertex)) {topologicalSortUtil(vertex, visited, stack);}}List<Vertex> sortedList = new ArrayList<>();while (!stack.isEmpty()) {sortedList.add(stack.pop());}return sortedList;}private void topologicalSortUtil(Vertex vertex, Set<Vertex> visited, Stack<Vertex> stack) {visited.add(vertex);for (Vertex neighbor : adjacencyList.get(vertex)) {if (!visited.contains(neighbor)) {topologicalSortUtil(neighbor, visited, stack);}}stack.push(vertex);}// 打印图的顶点和边public void printGraph() {for (Map.Entry<Vertex, List<Vertex>> entry : adjacencyList.entrySet()) {System.out.print(entry.getKey() + " -> ");for (Vertex vertex : entry.getValue()) {System.out.print(vertex + " ");}System.out.println();}}public static void main(String[] args) {DAG graph = new DAG();graph.addVertex("A");graph.addVertex("B");graph.addVertex("C");graph.addVertex("D");graph.addEdge("A", "B");graph.addEdge("A", "C");graph.addEdge("B", "D");graph.addEdge("C", "D");graph.addEdge("B", "A");System.out.println("图的顶点和边:");graph.printGraph();System.out.println("\n拓扑排序:");List<Vertex> sortedList = graph.topologicalSort();for (Vertex vertex : sortedList) {System.out.print(vertex + " ");}}
}

QA:待定

相关文章:

Java数据结构与算法(有向无环图)

前言 有向无环图&#xff08;Directed Graph&#xff09;是在有向图的基础上&#xff0c;增加无环的检查。 实现原理 使用邻接表表示法实现有向图相对简单明了&#xff0c;步骤也相对简单。 1:首先创建有向图 2.创建顶点 3.顶点间创建边 4.创建边的过程中检查节点是否存…...

QuanTA: 一种新的高秩高效微调范式

QuanTA方法的核心是利用张量操作来模拟量子电路中的门操作。这些张量被设计为仅在特定的轴上应用&#xff0c;类似于量子电路中的单量子比特或双量子比特门。通过这种方式&#xff0c;QuanTA能够以高秩参数化来适应LLMs的权重矩阵。 网址&#xff1a;QuanTA: 一种新的高秩高效微…...

【漏洞复现】用友NC downCourseWare 任意文件读取漏洞

0x01 产品简介 用友NC是一款企业级ERP软件。作为一种信息化管理工具&#xff0c;用友NC提供了一系列业务管理模块&#xff0c;包括财务会计、采购管理、销售管理、物料管理、生产计划和人力资源管理等&#xff0c;帮助企业实现数字化转型和高效管理。 0x02 漏洞概述 用友NC …...

度安讲 | 第二期「安全左移·业务护航」技术沙龙成功举办

当下&#xff0c;“安全左移”作为落地DevSecOps的重要实践之一&#xff0c;已在业界达成共识。DevSecOps作为一种集开发、安全、运维于一体的软件开发和运营模式&#xff0c;强调在敏捷交付下&#xff0c;“安全”在软件开发生命周期的全覆盖贯穿和核心位置。所谓“安全左移”…...

代码片段 | Matlab三维图显示[ R T 0 1] 的最佳方法

% 输入N组RT矩阵 N 4; R zeros(3, 3, N); T zeros(3, N); R(:,:,1) [-0.902608 0.250129 0.350335 ; 0.314198 0.939127 0.138996 ;-0.294242 0.235533 -0.926253 ]; T(:,1) [205.877;2796.02; 907.116];R(:,:,2) [-0.123936 0.643885 0.755018 ;0.816604 0.464468 -0.26…...

2024百度之星 跑步

原题链接&#xff1a;码题集OJ-跑步 题目大意&#xff1a;一个n个人在绕圈跑&#xff0c;第i个人跑一圈的时间是i分钟&#xff0c;每二个人位置相同就会打一次招呼&#xff0c;如果同时来到终点&#xff0c;他们就会停下来&#xff0c;请问会打多少次招呼&#xff1f; 思路&a…...

【git】TortoiseGitPlink Fatal Error 解决方法

背景 使用 TortoiseGit报错&#xff1a; TortoiseGitPlink Fatal Error No supported authentication methods available (server sent: publickey) 解决方法 1、有很多是重置git的秘钥解决的 2、重置ssh工具...

行心科技|中科利众:健康科技新合作,营养与科技融合前行

2024中国国际大健康产业文化节暨第34届国际大健康产业交易博览会于2024年5月31日在保利世贸博览馆盛大开幕&#xff0c;行心科技与中科利众&#xff08;贵州&#xff09;生物科技有限公司不谋而合&#xff0c;就“膳食机能健康问题解决方案”达成战略合作&#xff0c;共同开启膳…...

Xcode 打包报错Command PhaseScriptExecution failed with a nonzero exit code

解决办法: 1、在Xcode项目中 Pods -> Targets Support Files -> Pods-项目名 -> Pods-项目名-frameworks 中(大约在第44行) 加上 -f 2、CocoaPods版本太旧了,可以尝试升级CocoaPods版本 使用sudo gem update cocoapods更新cocoapods&#xff0c;问题将在1.12.1版本已…...

使用 IPSET 添加 CDN 节点 IP(IPv4/IPv6)到防火墙白名单

明月的服务器一直使用的是 iptables,随着近几年 IPv6 的普及&#xff0c;明月切身体会到还是 IPSET 最方便了&#xff0c;无论你是 IPv4 还是 IPv6 都可以方便的管理&#xff0c;无论你是加入白名单还是黑名单&#xff0c;都非常的简单高效&#xff01;今天就参照明月自己的实操…...

oracle trim 函数很慢,加trim以后执行超慢,执行计划求解

RT,该字段未建立索引&#xff0c;以下贴出SQL,及执行计划&#xff0c;不加trim走hash join&#xff0c;求解释&#xff01; ----------------------语句如下&#xff0c;标红的字段加trim() EXPLAIN PLAN FOR select a.楼盘id, a.监测明细id, a.报告日期, a.广告位名称, …...

【Leetcode Python】

偷某间房屋时&#xff0c;累积金额等于间隔前两间房的金额加上当前房的金额数&#xff1b;不偷时&#xff0c;累计金额就等于前一间房的金额数。 状态转移方程&#xff1a;dp[i] max(dp[i-2]nums[i], dp[i-1]) 并且注意错误点&#xff1a;dp[1]有两间房时&#xff0c;初始值为…...

Ubuntu系统的k8s常见的错误和解决的问题

K8s配置的时候出现的常见问题 Q1: master节点kubectl get nodes 出现的错误 或者 解决方法&#xff1a; cat <<EOF >> /root/.bashrc export KUBECONFIG/etc/kubernetes/admin.conf EOFsource /root/.bashrc重新执行 kubectl get nodes 记得需要查看一下自己的…...

Scala学习笔记7: 对象

目录 第七章 对象1- 单例对象2- 伴生对象3- 扩展类或特质的对象4- apply方法5- 应用程序对象6- 枚举end 第七章 对象 在Scala中, 对象(Obiect) 是一个单例实例, 类似于 Java中的单例模式 ; Scala中的对象使用 object 关键字定义, 它可以包含字段、方法、初始化代码和嵌套的类…...

【Linux】进程切换环境变量

目录 一.进程切换 1.进程特性 2.进程切换 1.进程切换的现象 2.如何实现 3.现实例子 2.环境变量 一.基本概念 二.常见环境变量 三.查询常见环境变量的方法 四.和环境变量相关的命令 五.环境变量表的组织方式 六.使用系统调用接口方式查询环境变量 1.getenv 2.反思 …...

嵌入式学习记录6.6(拷贝构造/友元函数/常成员函数)

一.拷贝构造函数和拷贝赋值函数 1.1拷贝构造函数功能,格式 拷贝构造函数是一种特殊的构造函数&#xff0c;用来将一个类对象给另一个类对象初始化使用的。 1> 用一个类对象给另一个类对象初始化时&#xff0c;会自动调用拷贝构造函数。 2> 当一个类对作为函数的实参&…...

宝塔 nginx 配置负载均衡 upstream

nginx 主配置文件加入 upstream myapp1 {server 192.168.124.101:5051;server 192.168.124.102:5052;server 192.168.124.111:5050;}站点配置文件中加入 location / {proxy_pass http://myapp1;}80端口映射到外网域名配置方法 加入红框中的代码 upstream myapp3 {server 192.16…...

idea 插件推荐

idea 插件推荐 RESTFul-Tool 接口搜索Show Comment 代码注释展示translation 翻译(注释翻译)MyBatisCodeHelperPro 日志封装sql xml跳转GitToolBox 展示GIT提交Jenkins Control idea jenkins 集成Gitmoji Plus: Commit Button GIT提交moji表情 RESTFul-Tool 接口搜索 https://…...

【Linux】Linux环境基础开发工具_5

文章目录 四、Linux环境基础开发工具Linux小程序---进度条git 未完待续 四、Linux环境基础开发工具 Linux小程序—进度条 上篇我们实现了一个简易的进度条&#xff0c;不过那仅仅是测试&#xff0c;接下来我们真正的正式实现一个进度条。 接着编写 processbar.c 文件 然…...

Java Web学习笔记15——DOM对象

DOM&#xff1a; 概念&#xff1a;Document Object Model&#xff1a; 文档对象模型 将标记语言的各个组成部分封装为对应的对象&#xff1a; Document: 整个文档对象 Element&#xff1a;元素对象 Attribute&#xff1a; 属性对象 Text&#xff1a;文本对象 Comment&a…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

【第二十一章 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 数据流…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

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

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

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...