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

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...