DFS算法查找所有路径详解
DFS算法查找所有路径详解
算法介绍
深度优先搜索(Depth-First Search,DFS)是一种图遍历算法,它从起始节点开始,沿着一条路径尽可能深入,直到达到最深的节点,然后回溯到前一节点,继续探索下一条路径。DFS通常使用递归或栈(非递归)来实现。
以下是DFS算法的基本步骤:
- 选择起始节点: 从图中选择一个起始节点作为当前节点;
- 标记节点: 标记当前节点为已访问,以防止重复访问;
- 探索邻居节点: 对于当前节点的未访问邻居节点,选择一个邻居节点作为新的当前节点,然后重复步骤2和步骤3;
- 回溯: 如果当前节点没有未访问的邻居节点,回溯到上一节点,重复步骤3;
- 重复过程: 重复步骤3和步骤4,直到所有节点都被访问。
递归实现的伪代码
function DFS(node):if node is not visited:mark node as visitedfor each neighbor of node:DFS(neighbor)
非递归实现的伪代码
DFS的非递归实现通常使用栈来模拟递归调用的过程,具体步骤如下:
- 创建一个空栈,并将起始节点压入栈中;
- 进入循环,直到栈为空;
- 弹出栈顶节点作为当前节点;
- 如果当前节点未访问,标记为已访问;
- 遍历当前节点的邻居节点,将未访问的邻居节点压入栈中;
- 重复步骤3到步骤5,直到栈为空为止。
注意:在处理连通图时可能导致栈溢出,因此在实际应用中可能需要注意栈深度的问题。
伪代码如下:
function DFS_non_recursive(start):stack = empty stackpush start onto stackwhile stack is not empty:current = pop from stackif current is not visited:mark current as visitedfor each neighbor of current:push neighbor onto stack
具体算法实现
由于可能存在非常多的路径,我们设置一个maxLength,表示限制经过的节点个数。
void Graph::DFS(int current, int end, std::unordered_set<int>& visited, std::vector<int>& path, int maxLength)
{static int currentLength = 0;static int i = 1;visited.insert(current);path.push_back(current);if (path.size() <= maxLength) {if (current == end){// 生成路径for (int node : path) {std::cout<<node<<' ';}std::cout<<"路径总长度为:"<<currentLength<<std::endl;}else{for (int neighbor = 0; neighbor < V; ++neighbor){if (adjMatrix[current][neighbor] != INF && visited.find(neighbor) == visited.end()) {int edgeWeight = adjMatrixLength[current][neighbor];currentLength += edgeWeight;DFS(neighbor, end, visited, path, maxLength);currentLength -= edgeWeight; // 回溯时减去当前边的长度}}}}visited.erase(current);path.pop_back();
}
相关文章:
DFS算法查找所有路径详解
DFS算法查找所有路径详解 算法介绍 深度优先搜索(Depth-First Search,DFS)是一种图遍历算法,它从起始节点开始,沿着一条路径尽可能深入,直到达到最深的节点,然后回溯到前一节点,继…...
单片机的存储、堆栈与程序执行方式
一、单片机存储区域 如图所示位STM32F103ZET6的参数: 单片机的ROM(内部FLASH):512KB,用来存放程序代码的空间。 单片机的RAM:64KB,一般都被分配为堆、栈、变量等的空间。 二、堆和栈的概念 …...
Web3开发成本和主要特性
多年来,技术不断进步,可帮助您的业务领先于竞争对手。如今,您可以看到许多更新和变化,使技术更加先进,对企业更加有用。到现在为止,web1.2和2.0比较流行,但是要知道web 3才是技术之父࿰…...
【数学建模美赛M奖速成系列】Matplotlib绘图技巧(一)
Matplotlib图像基础 写在前面1 基本绘图实例:sin、cos函数图2 plot()函数详解**kwargs参数: 3 matplotlib中绘图的默认配置4 设置图的横纵坐标的上下界5 设置横纵坐标上的记号6 调整图像的脊柱7 添加图例8 给一些特殊点加注释9 子图最后 写在前面 前面我…...
005、数据类型
1. 关于数据类型 Rust中,每个值都有其特定的数据类型,Rust会根据数据的类型来决定如何处理它们。 Rust是一门静态类型语言,它在编译程序的过程中就需要知道所有变量的具体类型。在大部分情况下,编译器可以根据我们如何绑定、使用变…...
软考网络工程师考试大纲(2018年最新版)
本书是全国计算机专业技术资格考试办公室组织编写的网络工程师考试大纲,本书除大纲内容外,还包括了人力资源和社会保障部、工业和信息化部的有关文件以及考试简介。 网络工程师考试大纲是针对本考试的计算机网络中级资格制定的。通过本考试的考生,可被用人单位择优聘任为工…...
【数据结构】栈【详解】
目录 栈的定义: 栈的声明与定义: 头文件的包含: 对栈的基本操作: 栈的初始化: 摧毁栈: 入栈: 编辑 出栈: 编辑 输出栈顶位置: 输出栈的当前大小: 判空操…...
CSS 纵向底部往上动画
<template><div class"container" mouseenter"startAnimation" mouseleave"stopAnimation"><!-- 旋方块 --><div class"box" :class"{ scale-up-ver-bottom: isAnimating }"><!-- 元素内容 --&g…...
常用的 MySQL 可视化客户端
数据库可视化客户端(GUI)让用户在和数据库进行交互时,能直观地查看、创建和修改对象,如:表、行和列。让数据库操作变得更方便了。 今天,我们来了解下目前市场上最常用的 MySQL 可视化客户端。 官方&#x…...
C#使用SyntaxTree获取.cs文件中的属性名和注释
有时候,我们可能需要获取.cs文件中的属性和对应的注释来生成一些代码,比如SQL查询什么的。 但使用正则匹配有时候会不准确。搜索了下,发现微软提供了代码解析的API。 具体如下两个方法: /// <summary> /// 获取所有属性和…...
基于价值认同的需求侧电能共享分布式交易策略(matlab完全复现)
目录 1 主要内容 2 部分程序 3 程序结果 4 下载链接 1 主要内容 该程序完全复现《基于价值认同的需求侧电能共享分布式交易策略》,针对电能共享市场的交易机制进行研究,提出了基于价值认同的需求侧电能共享分布式交易策略,旨在降低电力市…...
门控循环单元(GRU)-多输入回归预测
目录 一、程序及算法内容介绍: 基本内容: 亮点与优势: 二、实际运行效果: 三、部分程序: 四、全部代码数据分享: 一、程序及算法内容介绍: 基本内容: 本代码基于Matlab平台编译…...
电池管理系统BMS中SOC算法通俗解析(二)
下面简单介绍下我们BMS保护板使用的SOC估算方法。我们算法的主要是针对电流积分法计算SOC的局限性进行改进: ●电池包第一次上电使用开路电压法估算SOC。第一次上电,根据电池包厂家给出的电压和剩余容量二维关系图大概估算出目前电池包的剩余容量即SOC。…...
YOLOv5改进 | 2023主干篇 | 华为最新VanillaNet主干替换Backbone实现大幅度长点
一、本文介绍 本文给大家来的改进机制是华为最新VanillaNet网络,其是今年最新推出的主干网络,VanillaNet是一种注重极简主义和效率的神经网络架构。它的设计简单,层数较少,避免了像深度架构和自注意力这样的复杂操作(需要注意的是…...
爬虫工作量由小到大的思维转变---<第三十三章 Scrapy Redis 23年8月5日后会遇到的bug)>
前言: 收到回复评论说,按照我之前文章写的: 爬虫工作量由小到大的思维转变---<第三十一章 Scrapy Redis 初启动/conn说明书)>-CSDN博客 在启动scrapy-redis后,往redis丢入url网址的时候遇到: TypeError: ExecutionEngine.crawl() got an unexpected …...
PostgreSQL | 概念 | 什么是OLTPOLAP?
什么是OLTP&OLAP? 大白话理解:业务系统都可以称作OLTP,基于业务系统产生的数据进行数据分析和决策的都可以称为OLAP。 OLTP OLTP( Online Transaction Processing)在线事务处理系统 用途: 用于支持日…...
2023年成都市中等职业学校学生技能大赛“网络搭建及应用”赛项竞赛样卷
2023年成都市中等职业学校学生技能大赛 “网络搭建及应用”赛项竞赛样卷 (总分1000分) 目录 2023年成都市中等职业学校学生技能大赛 “网络搭建及应用”赛项竞赛样卷 网络建设与调试项目(500分) 服务器搭建与运维项目(…...
Angular进阶之六:Progressive rendering
简介 Progressive Rendering 是一种提高 Web 应用性能的方法,允许页面在加载过程中逐步呈现,以提高用户体验。在本文中,我们将探讨如何在 Angular 中通过自定义指令实现 Progressive Rendering,特别是处理从服务器获取大量数据的…...
机器人中的数值优化之线性共轭梯度法
欢迎大家关注我的B站: 偷吃薯片的Zheng同学的个人空间-偷吃薯片的Zheng同学个人主页-哔哩哔哩视频 (bilibili.com) 本文ppt来自深蓝学院《机器人中的数值优化》 目录 1.无约束优化方法对比 2.Hessian-vec product 3.线性共轭梯度方法的步长编辑 4.共轭梯度…...
嵌入式Linux C语言介绍
目录 一.前言 二.C语言的特点 一.前言 开发工具通常依赖于操作系统提供的各种功能和服务。许多开发工具都基于操作系统的API(应用程序接口)进行开发,这些API提供了文件处理、网络通信、图形界面等核心功能。没有操作系统的支持,…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
xmind转换为markdown
文章目录 解锁思维导图新姿势:将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件(ZIP处理)2.解析JSON数据结构3:递归转换树形结构4:Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...
鸿蒙HarmonyOS 5军旗小游戏实现指南
1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发,采用DevEco Studio实现,包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...
