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提供了文件处理、网络通信、图形界面等核心功能。没有操作系统的支持,…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
【Veristand】Veristand环境安装教程-Linux RT / Windows
首先声明,此教程是针对Simulink编译模型并导入Veristand中编写的,同时需要注意的是老用户编译可能用的是Veristand Model Framework,那个是历史版本,且NI不会再维护,新版本编译支持为VeriStand Model Generation Suppo…...
软件工程 期末复习
瀑布模型:计划 螺旋模型:风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合:模块内部功能紧密 模块之间依赖程度小 高内聚:指的是一个模块内部的功能应该紧密相关。换句话说,一个模块应当只实现单一的功能…...
C++_哈希表
本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说,直接开始吧! 一、基础概念 1. 哈希核心思想: 哈希函数的作用:通过此函数建立一个Key与存储位置之间的映射关系。理想目标:实现…...
jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...
