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

图论01-DFS和BFS(深搜和广搜邻接矩阵和邻接表/Java)

1.深度优先理论基础(dfs)

  • dfs的两个关键操作
搜索方向,是认准一个方向搜,直到碰壁之后再换方向
换方向是撤销原路径,改为节点链接的下一个路径,回溯的过程。
  • dfs解题模板
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择:本节点所连接的其他节点) {处理节点;dfs(图,选择的节点); // 递归回溯,撤销处理结果}
}
  • Java代码实现

邻接矩阵表示的图

public class DFSTraversalRecursive {private int[][] adjacencyMatrix; // 邻接矩阵private boolean[] visited; // 用于标记节点是否被访问过private int numNodes; // 节点数量public DFSTraversalRecursive(int[][] matrix) {this.adjacencyMatrix = matrix;this.numNodes = matrix.length;this.visited = new boolean[numNodes];}// 递归实现的深度优先搜索遍历public void dfsTraversalRecursive(int startNode) {visited[startNode] = true; // 标记当前节点为已访问System.out.print(startNode + " "); // 输出当前节点for (int i = 0; i < numNodes; i++) {// 如果存在从当前节点到节点 i 的边,并且节点 i 还未被访问过if (adjacencyMatrix[startNode][i] == 1 && !visited[i]) {dfsTraversalRecursive(i); // 递归调用,从节点 i 开始深度优先搜索}}}
}

邻接表表示的图

public class DFSTraversalAdjacencyList {private List<List<Integer>> adjacencyList; // 邻接表存储图的结构private boolean[] visited; // 标记节点是否被访问过// 构造函数,初始化邻接表和visited数组public DFSTraversalAdjacencyList(int numNodes) {this.adjacencyList = new ArrayList<>();for (int i = 0; i < numNodes; i++) {this.adjacencyList.add(new ArrayList<>());}this.visited = new boolean[numNodes];}// 添加边到邻接表public void addEdge(int source, int destination) {adjacencyList.get(source).add(destination);}// 递归实现的深度优先搜索遍历public void dfsTraversalRecursive(int startNode) {visited[startNode] = true; // 标记当前节点为已访问System.out.print(startNode + " "); // 输出当前节点// 遍历当前节点的所有邻居节点for (int neighbor : adjacencyList.get(startNode)) {if (!visited[neighbor]) {dfsTraversalRecursive(neighbor); // 递归调用,从邻居节点开始深度优先搜索}}}

2.广度优先搜索理论基础(bfs)

  • 使用场景
广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发,以起始点为中心一圈一圈进行搜索,一旦遇到终点,记录之前走过的节点就是一条最短路
  • Java代码实现

邻接矩阵表示的图

public class BFSTraversalAdjacencyMatrix {private int[][] adjacencyMatrix; // 邻接矩阵存储图的结构private boolean[] visited; // 标记节点是否被访问过public BFSTraversalAdjacencyMatrix(int numNodes) {this.adjacencyMatrix = new int[numNodes][numNodes]; // 初始化邻接矩阵this.visited = new boolean[numNodes]; // 初始化visited数组}// 添加边到邻接矩阵public void addEdge(int source, int destination) {adjacencyMatrix[source][destination] = 1;}// 广度优先搜索遍历public void bfsTraversal(int startNode) {Queue<Integer> queue = new LinkedList<>(); // 创建一个队列用于BFS遍历queue.add(startNode); // 将起始节点加入队列visited[startNode] = true; // 标记起始节点为已访问while (!queue.isEmpty()) {int currentNode = queue.poll(); // 出队列一个节点System.out.print(currentNode + " "); // 输出当前节点for (int i = 0; i < adjacencyMatrix.length; i++) {if (adjacencyMatrix[currentNode][i] == 1 && !visited[i]) {queue.add(i); // 将未访问的邻居节点加入队列visited[i] = true; // 标记邻居节点为已访问}}}}
}

邻接表表示的图

public class BFSTraversalAdjacencyList {private LinkedList<Integer>[] adjacencyList; // 邻接表存储图的结构private boolean[] visited; // 标记节点是否被访问过public BFSTraversalAdjacencyList(int numNodes) {// 初始化邻接表this.adjacencyList = new LinkedList[numNodes];for (int i = 0; i < numNodes; i++) {adjacencyList[i] = new LinkedList<Integer>();}// 初始化visited数组this.visited = new boolean[numNodes];}// 添加边到邻接表public void addEdge(int source, int destination) {adjacencyList[source].add(destination);}// 广度优先搜索遍历public void bfsTraversal(int startNode) {Queue<Integer> queue = new LinkedList<>(); // 创建一个队列用于BFS遍历queue.add(startNode); // 将起始节点加入队列visited[startNode] = true; // 标记起始节点为已访问while (!queue.isEmpty()) {int currentNode = queue.poll(); // 出队列一个节点System.out.print(currentNode + " "); // 输出当前节点for (int neighbor : adjacencyList[currentNode]) {if (!visited[neighbor]) {queue.add(neighbor); // 将未访问的邻居节点加入队列visited[neighbor] = true; // 标记邻居节点为已访问}}}}
}

相关文章:

图论01-DFS和BFS(深搜和广搜邻接矩阵和邻接表/Java)

1.深度优先理论基础(dfs) dfs的两个关键操作 搜索方向&#xff0c;是认准一个方向搜&#xff0c;直到碰壁之后再换方向 换方向是撤销原路径&#xff0c;改为节点链接的下一个路径&#xff0c;回溯的过程。dfs解题模板 void dfs(参数) {if (终止条件) {存放结果;return;}for …...

【Python】Miniconda+Vscode+Jupyter 环境搭建

1.安装 Miniconda Conda 是一个开源的包管理和环境管理系统&#xff0c;可在 Windows、macOS 和 Linux 上运行&#xff0c;它可以快速安装、运行和更新软件包及其依赖项。使用 Conda&#xff0c;我们可以轻松在本地计算机上创建、保存、加载和切换不同的环境 Conda 分为 Anaco…...

Redis消息队列与thinkphp/queue操作

业务场景 场景一 用户完成注册后需要发送欢迎注册的问候邮件、同时后台要发送实时消息给用户对应的业务员有新的客户注册、最后将用户的注册数据通过接口推送到一个营销用的第三方平台。 遇到两个问题&#xff1a; 由于代码是串行方式&#xff0c;流程大致为&#xff1a;开…...

【Ubuntu】常用命令

一般操作 pwd&#xff08;present working directory&#xff09; 显示当前的工作目录/路径。 cd (change directory) 改变目录&#xff0c;用于输入需要前往的路径/目录。 有一些特殊命令也很常用 : 解释 前往同一级的另一个目录 cd ../directory name cd .. 表示进入上…...

稀碎从零算法笔记Day22-LeetCode:

题型&#xff1a;链表 链接&#xff1a;2. 两数相加 - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1a;Leet 题目描述 给你两个 非空 的链表&#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的&#xff0c;并且每个节点只能存储 一位 数字。 …...

Nacos下载和安装

&#xff08;1&#xff09;下载地址和版本 下载地址&#xff1a;Releases alibaba/nacos GitHub 解压在没有中文及空格的文件夹 &#xff08;2&#xff09;启动nacos服务 在bin目录下,打开命令行,输入 启动命令&#xff1a;sh startup.sh -m standalone - Linux/Unix/Mac …...

pandas简介(python)

pandas是什么 Pandas 是一个开源的第三方 Python 库&#xff0c;从 Numpy 和 Matplotlib 的基础上构建而来&#xff0c;享有数据分析“三剑客之一”的盛名&#xff08;NumPy、Matplotlib、Pandas&#xff09;。Pandas 已经成为 Python 数据分析的必备高级工具&#xff0c;它的…...

个人网站制作 Part 13 添加搜索功能[Elasticsearch] | Web开发项目

文章目录 &#x1f469;‍&#x1f4bb; 基础Web开发练手项目系列&#xff1a;个人网站制作&#x1f680; 添加搜索功能&#x1f528;使用Elasticsearch&#x1f527;步骤 1: 安装Elasticsearch&#x1f527;步骤 2: 配置Elasticsearch&#x1f527;步骤 3: 创建索引 &#x1f…...

Springboot+vue的仓库管理系统(有报告)。Javaee项目,springboot vue前后端分离项目。

演示视频&#xff1a; Springbootvue的仓库管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot vue前后端分离项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层…...

vue3 + vite 实现一个动态路由加载功能

假设后端返回的格式是这样子 {"menu": [{"path": "/admin","name": "adminLayout","redirect": "/admin/index","componentPath": "/layout/admin/index.vue","children&quo…...

【征稿进行时|见刊、检索快速稳定】2024年区块链、物联网与复合材料与国际学术会议 (ICBITC 2024)

【征稿进行时|见刊、检索快速稳定】2024年区块链、物联网与复合材料与国际学术会议 (ICBITC 2024) 大会主题: (主题包括但不限于, 更多主题请咨询会务组苏老师) 区块链&#xff1a; 区块链技术和系统 分布式一致性算法和协议 块链性能 信息储存系统 区块链可扩展性 区块…...

若依jar包运行脚本,从零到一:用Bash脚本实现JAR应用的启动、停止与监控

脚本使用说明&#xff1a; 启动应用&#xff1a;sh app.sh start停止应用&#xff1a;sh app.sh stop检查应用状态&#xff1a;sh app.sh status重启应用&#xff1a;sh app.sh restart 注意事项&#xff1a; 请确保你的系统上安装了 Java 环境&#xff0c;并且 ruoyi-admin…...

Unix运维_FreeBSD-13.1临时环境变量设置(bin和include以及lib)

Unix运维_FreeBSD-13.1临时环境变量设置(bin和include以及lib) 在 FreeBSD 系统上设置用户环境变量可以通过编辑用户的 Shell配置文件 来实现。 cshrc 与 csh_profile 的区别: cshrc: 每个脚本执行前都执行一遍这个脚本。 csh_profile: 根据不同使用者用户名, 会先去其 home…...

Apache Dolphinscheduler - 无需重启 Master-Server 停止疯狂刷日志解决方案

记录的是一个 3.0 比较难搞的问题&#xff0c;相信不少使用过 3.0 的用户都遇到过 Master 服务中存在一些工作流或者任务流一直不停的死循环的问题&#xff0c;导致疯狂刷日志。不过本人到现在也没找到最关键的触发原因&#xff0c;只是看到一些连锁反应带来的结果…… 影响因素…...

竞争优势:大型语言模型 (LLM) 如何重新定义业务策略

人工智能在内容创作中的突破 在当今快节奏的商业环境中&#xff0c;像 GPT-4 这样的大型语言模型 (LLM) 不再只是一种技术新颖性&#xff1b; 它们已成为重新定义跨行业业务战略的基石。 从增强客户服务到推动创新&#xff0c;法学硕士提供了企业不容忽视的竞争优势。 1. 加强…...

Spring AOP和AspectJ AOP区别

Spring AOP&#xff08;Aspect-Oriented Programming&#xff09;和 AspectJ AOP 是两种不同的 AOP 实现方式&#xff0c;它们在实现上有一些区别。下面是它们之间的主要区别&#xff1a; 基于代理 vs 字节码增强&#xff1a; Spring AOP&#xff1a; Spring AOP 是基于代理的…...

FREERTOS信号量详解

信号量是操作系统中重要的一部分&#xff0c;信号量一般用来进行资源管理和任务同步&#xff0c;资源管理其实就是用变量来标记现有资源的数量&#xff0c;任务同步其实就是用标志位来控制任务的先后执行顺序&#xff0c;这些概念在操作系统中以及裸机开发中都有所涉及。 FreeR…...

每天学习一个Linux命令之vim

每天学习一个Linux命令之vim Vim是一款功能强大的文本编辑器&#xff0c;在Linux系统中广泛使用。本篇博客将介绍一些常用的Vim命令及其选项&#xff0c;帮助您更好地使用Vim进行文本编辑。 命令及选项 以下是Vim的常用命令及其可用选项&#xff1a; 1. 打开文件 $ vim fi…...

linux环境部署

war包环境 在Linux系统上部署准备war包环境 查看linux当前版本和系统类型 [rootlocalhost ~]# uname -a Linux localhost.localdomain 3.10.0-1160.el7.x86_64 #1 SMP Mon Oct 19 16:18:59 UTC 2020 x86_64 x86_64 x86_64 GNU/Linuxlinux 打包文件夹 使用tar命令&#xff1…...

上位机图像处理和嵌入式模块部署(qmacvisual图像预处理)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 不管大家是在读书的时候学习的图像处理&#xff0c;还是在后来的工作中&#xff0c;重新学习了图像处理&#xff0c;相信大家对图像预处理的概念并…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...