当前位置: 首页 > 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…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》

&#x1f9e0; LangChain 中 TextSplitter 的使用详解&#xff1a;从基础到进阶&#xff08;附代码&#xff09; 一、前言 在处理大规模文本数据时&#xff0c;特别是在构建知识库或进行大模型训练与推理时&#xff0c;文本切分&#xff08;Text Splitting&#xff09; 是一个…...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...

【字节拥抱开源】字节团队开源视频模型 ContentV: 有限算力下的视频生成模型高效训练

本项目提出了ContentV框架&#xff0c;通过三项关键创新高效加速基于DiT的视频生成模型训练&#xff1a; 极简架构设计&#xff0c;最大化复用预训练图像生成模型进行视频合成系统化的多阶段训练策略&#xff0c;利用流匹配技术提升效率经济高效的人类反馈强化学习框架&#x…...

大模型智能体核心技术:CoT与ReAct深度解析

**导读&#xff1a;**在当今AI技术快速发展的背景下&#xff0c;大模型的推理能力和可解释性成为业界关注的焦点。本文深入解析了两项核心技术&#xff1a;CoT&#xff08;思维链&#xff09;和ReAct&#xff08;推理与行动&#xff09;&#xff0c;这两种方法正在重新定义大模…...

SDU棋界精灵——硬件程序ESP32实现opus编码

一、 ​​音频处理框架​ 该项目基于Espressif的音频处理框架构建,核心组件包括 ESP-ADF 和 ESP-SR,以下是完整的音频处理框架实现细节: 1.核心组件 (1) 音频前端处理 (AFE - Audio Front-End) ​​main/components/audio_pipeline/afe_processor.c​​功能​​: 声学回声…...