leetcode797图论-对邻接矩阵和邻接表不同形式进行dfs与bfs遍历方法
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
示例 1：
输入：graph = [[1,2],[3],[3],[]] 输出：[[0,1,3],[0,2,3]] 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
本题输入方式为邻接表方式输入
对于邻接表方式解题方法：
1、DFS遍历
2、BFS遍历
DFS遍历实现代码（基于邻接表）
class Solution {List<Integer> path=new ArrayList<>();List<List<Integer>> result=new ArrayList<>();public List<List<Integer>> allPathsSourceTarget(int[][] graph) {path.add(0);dfs(graph,0);return result;}private void dfs(int[][] graph,int x){if(x==graph.length-1){result.add(new ArrayList<>(path));return;}for(int i=0;i<graph[x].length;i++){path.add(graph[x][i]);dfs(graph,graph[x][i]);path.remove(path.size()-1);}}
}BFS遍历实现代码（基于邻接表）
import java.util.*;class Solution {public List<List<Integer>> allPathsSourceTarget(int[][] graph) {List<List<Integer>> result = new ArrayList<>();int target = graph.length - 1;// BFS队列：存储（当前节点，路径）Queue<List<Integer>> queue = new LinkedList<>();// 初始路径：0List<Integer> initialPath = new ArrayList<>();initialPath.add(0);queue.offer(initialPath);while (!queue.isEmpty()) {List<Integer> currentPath = queue.poll();int lastNode = currentPath.get(currentPath.size() - 1);// 到达目标节点if (lastNode == target) {result.add(new ArrayList<>(currentPath));continue;}// 遍历邻接表中的所有邻居for (int neighbor : graph[lastNode]) {List<Integer> newPath = new ArrayList<>(currentPath); // 复制路径newPath.add(neighbor);queue.offer(newPath);}}return result;}
}图论题目中除了邻接表还有邻接矩阵形式，可以将邻接表转换为邻接矩阵形式更为直观清晰。
邻接矩阵方式解题方法：
1、DFS遍历
2、BFS遍历
DFS遍历实现代码（基于邻接矩阵）
import java.util.*;class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();int[][] adjacencyMatrix; // 邻接矩阵public List<List<Integer>> allPathsSourceTarget(int[][] graph) {// 1. 将邻接表转换为邻接矩阵int n = graph.length;adjacencyMatrix = new int[n][n];for (int i = 0; i < n; i++) {for (int neighbor : graph[i]) {adjacencyMatrix[i][neighbor] = 1; // 标记存在边}}// 2. 从节点0开始DFSpath.add(0);dfs(0, n - 1);return result;}private void dfs(int current, int target) {if (current == target) {result.add(new ArrayList<>(path)); // 找到一条路径return;}for (int next = 0; next < adjacencyMatrix.length; next++) {if (adjacencyMatrix[current][next] == 1) { // 如果存在边path.add(next);dfs(next, target);path.remove(path.size() - 1); // 回溯}}}
}BFS遍历实现代码（基于邻接矩阵）
import java.util.*;class Solution {public List<List<Integer>> allPathsSourceTarget(int[][] graph) {List<List<Integer>> result = new ArrayList<>();int n = graph.length;// 1. 将邻接表转换为邻接矩阵int[][] adjacencyMatrix = new int[n][n];for (int i = 0; i < n; i++) {for (int neighbor : graph[i]) {adjacencyMatrix[i][neighbor] = 1;}}// 2. BFS初始化：队列存储（当前节点，路径）Queue<Pair<Integer, List<Integer>>> queue = new LinkedList<>();List<Integer> initialPath = new ArrayList<>();initialPath.add(0);queue.offer(new Pair<>(0, initialPath));// 3. BFS遍历while (!queue.isEmpty()) {Pair<Integer, List<Integer>> current = queue.poll();int node = current.getKey();List<Integer> path = current.getValue();if (node == n - 1) {result.add(new ArrayList<>(path)); // 找到一条路径continue;}// 遍历所有邻接节点for (int next = 0; next < n; next++) {if (adjacencyMatrix[node][next] == 1) {List<Integer> newPath = new ArrayList<>(path); // 复制路径newPath.add(next);queue.offer(new Pair<>(next, newPath));}}}return result;}// 辅助Pair类（Java 14+可用java.util.Record替代）static class Pair<K, V> {K key;V value;Pair(K key, V value) {this.key = key;this.value = value;}K getKey() { return key; }V getValue() { return value; }}
}
相关文章：
leetcode797图论-对邻接矩阵和邻接表不同形式进行dfs与bfs遍历方法
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序） graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向…...
Spark核心架构与RDD：大数据处理的基石
Apache Spark作为新一代分布式计算引擎，其高效性和灵活性源于独特的运行架构与核心数据结构RDD。本文简要解析Spark的核心组件及RDD的核心特性，帮助开发者快速理解其设计思想。 一、Spark运行架构 Spark采用标准的**Master-Slave架构，核心组…...
Python Orange：托拉拽玩转机器学习、数据挖掘！
相比写代码做数据挖掘，Python Orange简直是懒人和新手的救星！传统编程得敲一行行代码，调库、debug 累得要死，而Orange靠拖拽就能搞定数据导入、清洗、可视化、建模、评估和无监督学习，支持跨Windows、Mac、Linux平台随…...
K8S学习之基础七十七：istio实现超时功能
istio实现超时功能 模拟客户端调用 nginx，nginx 将请求转发给 tomcat。nginx 服务设置了超时时间为2秒，如果超出这个时间就不在等待，返回超时错误。tomcat服务设置了响应时间延迟10秒，任何请求都需要等待10秒后才能返回。client …...
EFA-YOLO：一种高效轻量的火焰检测模型解析
论文地址：https://arxiv.org/pdf/2409.12635 目录 论文地址：https://arxiv.org/pdf/2409.12635 一、论文结构解析 二、核心创新点解读 1. EAConv（高效注意力卷积） 2. EADown（高效下采样） 三、实验结果对比 1. 精度指标对比 2. 实际检测效果 四、应用场景展望 …...
PyQt6实例_A股财报数据维护工具_解说并数据与完整代码分享
目录 1 20250403之前的财报数据 2 整个项目代码 3 工具使用方法 3.1 通过akshare下载 3.2 增量更新 3.3 查看当前数据情况 3.4 从数据库中下载数据 视频 1 20250403之前的财报数据 通过网盘分享的文件：财报三表数据20250403之前.7z 链接: https://pan.ba…...
【AAOS】【源码分析】CarAudioService（二）-- 功能介绍
汽车音频是 Android 汽车操作系统 (AAOS) 的一项功能，允许车辆播放信息娱乐声音，例如媒体、导航和通信。AAOS 不负责具有严格可用性和时间要求的铃声和警告，因为这些声音通常由车辆的硬件处理。将汽车音频服务集成在汽车中，彻底改变了驾驶体验，为驾驶员和乘客提供了音乐、…...
Python星球日记 - 第18天：小游戏开发（猜数字游戏）
🌟引言： 上一篇：Python星球日记 - 第17天：数据可视化 名人说：路漫漫其修远兮，吾将上下而求索。（屈原《离骚》） 创作者：Code_流苏(CSDN)（一个喜欢古诗词和编程…...
+异常处理)
ShopXO v2.2.4开源商城手动部署(保姆级)+异常处理
ShopXO v2.2.4开源商城手动部署(保姆级) 1.项目了解 1.1项目简洁 ShopXO国内领先企业级免费开源电商系统！ 求实进取、创新专注、自主研发、国内领先企业级电商系统解决方案。遵循MIT开源协议发布，无需授权、可商用、可二次开发、满足99%的电商运营需…...
Android Studio - 解决 Please Select Android SDK
一、出现的问题 点击 Run 后弹窗，图一位置出现图二提示。 二、解决办法 进入 Tools -> SDK Manager，在 Android SDK Location 点击 Edit，一直 Next 就解决了。...
Java 列表初始化全解析：7种方式详解与最佳实践
文章目录 **引言****1. 传统逐个添加元素****特点****注意事项** **2. Arrays.asList() 构造函数****特点****注意事项** **3. 双括号初始化（匿名内部类）****特点****注意事项** **4. Java 9 List.of()（不可变列表）****特点****注…...
python之安装PaddlePaddle和PaddleX解析pdf表格
目录标题 飞桨PaddlePaddle本地安装教程1-1. 基于 Docker 安装飞桨1-2. 基于 pip 安装飞桨2. 我两个环境 都选择的是pip 安装10. 如果报错10. 离线安装 飞桨PaddlePaddle本地安装教程 源码下载：https://github.com/PaddlePaddle/PaddleX/blob/release/3.0-beta1/do…...
MLA（Multi-Level Adaptive）融合算子全院级医疗编程探析（代码版）
MLA（Multi-Level Adaptive）融合算子的AI医疗技术原理、实现方法及医疗应用场景的深度解析： 一、MLA融合算子技术本质 1. 核心设计理念 MLA是一种硬件感知的算子重组技术，通过打破传统深度学习框架的算子边界，实现&a…...
Python----概率论与统计（概率论，互斥事件和概率和，非互斥事件和概率和，独立性事件，生日问题，条件概率）
一、概率论 1.1、概率论 概率论是研究随机现象的一门数学学科。它为不确定性提供了一个量化的框架，允许我们衡量事件发生的可能性。 概率论研究随机现象，用于量化和分析不确定性。它的基本概念包括： 样本空间（Sample Space&…...
Ubuntu24.04 编译 Qt 源码
一：Ubuntu 把 Qt 拆成了多个源码包： 1. 基础包 2. 可选包 二：编译 qtbase-opensource-src 1. 配置源（修改 /etc/apt/sources.list.d/ubuntu.sources) 2. 下载代码 apt source qtbase-opensource-src3. 安装依赖 sudo a…...
数据库无法插入中文字符
INSERT INTO book VALUES (1, ‘楚辞’, ‘屈原’, ‘中国文联出版社’, ‘0’) 1366 - Incorrect string value: ‘\xE6\xA5\x9A\xE8\xBE\x9E’ for column ‘name’ at row 1 查询时间: 0 秒 查看字符集设置 SHOW VARIABLES LIKE character_set%; SHOW VARIABLES LIKE colla…...
在Ubuntu系统如何让MySQL服务器支持远程连接
目录 问题描述 解决方案 步骤一：检查MySQL配置文件 编辑 步骤二：修改bind-address参数 编辑 步骤三：重启MySQL服务 步骤四：验证更改 步骤五：检查防火墙设置 步骤六：测试远程连接 注意事项 …...
【期中准备】电路基础（西电）
电路 题型：填空，简答（概念），计算 PPT 1.X 电压和电流的参考方向一致，称为关联参考方向 消耗功率为正数：负载和电源由功率正负来定义 电路中所有原件功率之和为0（“自产自销”&#…...
mysql 重复读自己事务中可以看到新插入数据
推荐好文 吃透MySQL（六）：事务详细介绍 地址转发https://blog.csdn.net/u013277209/article/details/113585022 开启客户端 mysql -u 账号名 -p 输入密码 在一个 事务中 mysql> set session transaction isolation level repeatable…...
Java后端开发-面试总结（集结版）
第一个问题，在 Java 集合框架中，ArrayList和LinkedList有什么区别？在实际应用场景中，应该如何选择使用它们？ ArrayList 基于数组，LinkedList 基于双向链表。 在查询方面 ArrayList 效率高，添加…...
Python第八章03：Pyecharts快速入门
# pyecharts快速入门# 一、折线图基础应用# 导入python包 from pyecharts.charts import Line from pyecharts.options import TitleOpts,LegendOpts,ToolboxOpts,VisualMapOpts,TooltipOpts,DataZoomOpts# 创建一个折线图对象 line Line() # 给折线图对象添加x、y轴的数据 l…...
)
BUUCTF-web刷题篇(17)
26.BabyUpload 源码：https://github.com/imaginiso/GXY_CTF/tree/master/Web/babyupload 查看题目源码： 写着：SetHandler application/x-httpd-php 通过源码可以看出这道文件上传题目主要还是考察.htaccess配置文件的特性，倘若…...
openfga原理及简单落地方案设计
源码地址 https://github.com/openfga OpenFGA 是一款高性能且灵活的授权/许可引擎，专为开发人员打造，灵感来自Google Zanzibar。它将强大的基于关系的访问控制 (ReBAC)和基于属性的访问控制 (ABAC)概念与领域特定语言相结合，可以轻松制定可以扩展和发展到任何规模的任何用例…...
混合并行技术在医疗AI领域的应用分析（代码版）
混合并行技术（专家并行/张量并行/数据并行）通过多维度的计算资源分配策略，显著提升了医疗AI大模型的训练效率与推理性能。以下结合技术原理与医疗场景实践，从策略分解、技术对比、编排优化及典型案例等维度展开分析： 一、混合并行技术：突破单卡算力限制 1. 并行策略三维分…...
深信服安全运营面试题
《网安面试指南》https://mp.weixin.qq.com/s/RIVYDmxI9g_TgGrpbdDKtA?token1860256701&langzh_CN 5000篇网安资料库https://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247486065&idx2&snb30ade8200e842743339d428f414475e&chksmc0e4732df793fa3bf39…...
基于IDEA+SpringBoot+Mave+Thymeleaf的系统实现
一. 安装IntelliJ IDEA 下载并安装IntelliJ IDEA Ultimate或Community版 2024年最新版IntelliJ IDEA下载安装过程（含Java环境搭建） 二、下载 Maven 访问官网下载 打开浏览器，访问 Maven 官方下载页面： Download Apache Maven –…...
用Python爬虫抓取数据并保存为JSON的完整指南
本文将深入探讨如何利用Python爬虫技术抓取网页数据，并通过专业的数据处理流程将其保存为JSON格式。我们将以电商网站产品数据抓取为例，演示从基础实现到生产级优化的完整流程，涵盖反爬策略应对、数据清洗和大规模存储等关键环节。 一、环境…...
Tigshop| 一个基于Java的开源商城系统
在电商竞争愈发激烈的当下，一个强大且适配的商城系统是商家制胜的法宝 Tigshop官网 - 开源商城系统https://www.tigshop.com/ 一、卓越技术根基 前端体验升级 Tigshop 运用 Vue3 与 TypeScript 搭建前端。Vue3 的响应式系统和 Composition API，让页…...
Windows 部署项目 apache + mod_wsgi，nginx + waitress
文章目录 1、apache mod_wsgi，nginx waitress两种部署方式的区别2、以nginx waitress为例 有些项目必须部署在windows上，有IIS wfastcgi、apache mod_wsgi，nginx waitress部署方式 1、apache mod_wsgi，nginx waitress两种…...
RabbitMQ惰性队列的工作原理、消息持久化机制、同步刷盘的概念、延迟插件的使用方法
惰性队列工作原理 惰性队列通过尽可能多地将消息存储到磁盘上来减少内存的使用。与传统队列相比，惰性队列不会主动将消息加载到内存中，而是尽量让消息停留在磁盘上，从而降低内存占用。尽管如此，它并不保证所有操作都是同步写入磁…...
Prompt_Engineering提示词工程（一）
一、Prompt（提示词） Prompt（提示词）是给AI模型交互文本片段，用于指导模型生成符合预期输出结果，提示词的目的是为模型提供一个上下文的任务，以便模型能够更准确地理解用户的意图，并…...
探索 Shell 中的扩展通配符：从 Bash 到 Zsh
在 Unix 系统中，通配符（globbing）是 shell 的核心功能，用于快速匹配文件或目录。基础通配符（如 *、?、[]）虽简单实用，但在复杂场景下往往力不从心。为此，许多现代 shell 提供了“扩…...
电脑清洁常用工具
清洁布：用于擦拭电脑表面和屏幕。一般选择柔软、不掉毛的微纤维清洁布，它能有效去除灰尘和污渍，同时不会刮伤电脑表面。压缩空气罐：可以产生强力气流，用于吹走电脑内部的灰尘，如主机箱、键盘缝隙等部位的灰…...
深入理解Spring是如何解决循环依赖的
1、简介循环依赖 在 Spring 框架中，循环依赖是指两个或多个 Bean 互相依赖，形成了一个闭环。例如，Bean A 依赖于 Bean B，而 Bean B 又依赖于 Bean A。这种依赖关系可能会导致初始化失败。Spring 提供了一种机制来解决这种循环依赖…...
AIGC时代的新风口！MCP协议引领未来无限可能
文章目录 一、引言二、MCP的定义与架构三、MCP的使用案例1. Cursor MCP Figma：工程化项目自动化2. Claude Desktop与本地文件系统交互3. 智能客服系统中的MCP应用 四、MCP的应用前景1. 更广泛的应用场景拓展2. 更高的性能要求和优化3. 更强的安全性和隐私保护措施…...
)
NO.81十六届蓝桥杯备战|数据结构-Trie树-字典树-前缀树|于是他错误的点名开始了|最大异或对 The XOR Largest Pair(C++)
字典树的概念 Trie树⼜叫字典树或前缀树，是⼀种能够快速插⼊和查询字符串的数据结构。它利⽤字符串的公共前缀，将字符串组织成⼀棵树形结构，从⽽⼤⼤提⾼了存储以及查找效率。 我们可以把字典树想象成⼀棵多叉树，每⼀条边代表⼀个…...
go语言应该如何学习
以下是学习Go语言的高效路径及关键技巧，结合多个优质来源整理而成，适合不同基础的学习者： 一、基础语法快速入门（1-2周） 1、环境搭建 下载安装Go SDK，配置GOPATH和GOROOT环境变量，推荐使用Go…...
struct结构体、union联合体和枚举
目录 一、结构体的声明和使用 1.1 结构体正常声明和创建 1.2 结构体特殊声明 1.3 结构体的自引用 二、结构体内存对齐 2.1 对齐规则 2.2 #pragma修改 三、结构体传参 四、结构体位段 4.1 位段内存分配 4.2 位段内存应用 五、结构体中的柔性数组概念 六、union联合…...
el-tree 实现树形菜单子级取消选中后父级选中效果不变
背景 在复杂的企业级管理系统中，树形菜单是一种常见的数据展示和交互组件。传统的树形菜单通常存在以下交互局限： 子节点取消选中时，父节点会自动取消选中无法满足复杂的权限分配和数据筛选场景实际应用场景： 组织架构权限管理多层级资源分配复杂的数据筛选与展示实现需求…...
centos7系统搭建nagios监控
~监控节点安装 1. 系统准备 1.1 更新系统并安装依赖 sudo yum install -y httpd php php-cli gcc glibc glibc-common gd gd-devel make net-snmp openssl-devel wget unzip sudo yum install -y epel-release # 安装 EPEL 仓库 sudo yum install -y automake autoconf lib…...
Gitlab的迁移升级
Gitlab11.6.5的迁移升级 Gitlab升级是不能跨大版本升级的，根据官方升级路径来操作。 gitlab迁移 首先需要查看当前gitlab版本 cat /opt/gitlab/embedded/service/gitlab-rails/VERSION 当前版本是11.6.5 备份源数据 原仓库备份所有的文件 /opt/gitlab/bin/git…...
C++11QT复习 （十九）
文章目录 Day13 C 时间库和线程库学习笔记（Chrono 与 Thread）一、时间库 <chrono>1.1 基本概念1.2 使用示例1.3 duration 字面量单位 二、线程库 <thread>2.1 基本用法2.2 数据竞争（Race Condition）2.3 加锁ÿ…...
3 版本控制：GitLab、Jenkins 工作流及分支开发模式实践
一、引言 在软件开发过程中，版本控制是保障代码质量、提高开发效率的关键环节。有效的版本控制能够帮助团队成员更好地协作，追踪代码变更，快速定位和解决问题。GitLab 和 Jenkins 作为两款广泛使用的工具，在版本控制和持续集成 / 持续部署（CI/CD）流程中发挥着重要作用。本…...
docker配置远程连接，dockerfile-maven-plugin插件打包到远程
我开发机器上的内存不大，能不安装在本地的应用就都跑在服务器上了，但是本地打包时需要用到docker打包成镜像，这时会本地运行docker，所以准备本地只使用docker客户端，连接服务器上的docker服务端 服务端配置 docker服…...
Skyline配置指南-微信小程序
Skyline 是微信小程序推出的新一代渲染引擎，提供了更强大的渲染能力和更流畅的性能体验。以下是配置 Skyline 的详细步骤： 一、app.json文件配置 "componentFramework": "glass-easel", "lazyCodeLoading": "requi…...
【c语言】倒置字符串
将一句话的单词进行倒置，符号不变，用例长度不超过100 思路： 逆序整个字符串逆序每个单词 #include <stdio.h> #include <string.h> void reverse(char* left, char* right) {while (left < right) {//char *tmp left;//error…...
MySQL多表查询实战指南：从SQL到XML映射的完整实现（2W+字深度解析）
MySQL多表查询实战指南：从SQL到XML映射的完整实现（2W+字深度解析） 第一章 多表查询基础与核心原理 1.1 关系型数据库设计范式 以电商系统为例的三范式实践： -- 原始数据表（违反第三范式） CREATE TABLE orders (order_id INT PRIMARY KEY,customer_name VARCHAR(50),p…...
【图书管理系统】全栈开发图书管理系统获取图书列表接口（后端：计算图书页数、查询当前页展示的书籍）
图书列表 实现服务器代码(计算图书总数量查询当前页需要展示的书籍) 后端响应时，需要响应给前端的数据 records：第 pageNum 页要展示的图书有哪些（存储到List集合中）total：计算一共有多少本书（用于告诉前…...
SpringMvc的请求-获得请求参数
客户端请求参数的格式是: namevalue&namevalue..… 服务器端要获得请求的参数，有时还需要进行数据的封装，SpringMVC可以接收如下类型的参数: 基本类型参数 POJO类型参数 数组类型参数 集合类型参数 获得基本类型参数 Controller中的业务方法…...
CSS 笔记——Flexbox（弹性盒布局）
目录 1. Flex 容器与 Flex 项目 2. 主轴与交叉轴 3. Flex 容器的属性 display flex-direction justify-content align-items align-content flex-wrap 4. Flex 项目的属性 flex-grow flex-shrink flex-basis flex align-self 5. Flexbox 的优点 6. Flexbox 的…...