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

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算法查找所有路径详解 算法介绍 深度优先搜索&#xff08;Depth-First Search&#xff0c;DFS&#xff09;是一种图遍历算法&#xff0c;它从起始节点开始&#xff0c;沿着一条路径尽可能深入&#xff0c;直到达到最深的节点&#xff0c;然后回溯到前一节点&#xff0c;继…...

单片机的存储、堆栈与程序执行方式

一、单片机存储区域 如图所示位STM32F103ZET6的参数&#xff1a; 单片机的ROM&#xff08;内部FLASH&#xff09;&#xff1a;512KB&#xff0c;用来存放程序代码的空间。 单片机的RAM&#xff1a;64KB&#xff0c;一般都被分配为堆、栈、变量等的空间。 二、堆和栈的概念 …...

Web3开发成本和主要特性

多年来&#xff0c;技术不断进步&#xff0c;可帮助您的业务领先于竞争对手。如今&#xff0c;您可以看到许多更新和变化&#xff0c;使技术更加先进&#xff0c;对企业更加有用。到现在为止&#xff0c;web1.2和2.0比较流行&#xff0c;但是要知道web 3才是技术之父&#xff0…...

【数学建模美赛M奖速成系列】Matplotlib绘图技巧(一)

Matplotlib图像基础 写在前面1 基本绘图实例&#xff1a;sin、cos函数图2 plot()函数详解**kwargs参数&#xff1a; 3 matplotlib中绘图的默认配置4 设置图的横纵坐标的上下界5 设置横纵坐标上的记号6 调整图像的脊柱7 添加图例8 给一些特殊点加注释9 子图最后 写在前面 前面我…...

005、数据类型

1. 关于数据类型 Rust中&#xff0c;每个值都有其特定的数据类型&#xff0c;Rust会根据数据的类型来决定如何处理它们。 Rust是一门静态类型语言&#xff0c;它在编译程序的过程中就需要知道所有变量的具体类型。在大部分情况下&#xff0c;编译器可以根据我们如何绑定、使用变…...

软考网络工程师考试大纲(2018年最新版)

本书是全国计算机专业技术资格考试办公室组织编写的网络工程师考试大纲,本书除大纲内容外,还包括了人力资源和社会保障部、工业和信息化部的有关文件以及考试简介。 网络工程师考试大纲是针对本考试的计算机网络中级资格制定的。通过本考试的考生,可被用人单位择优聘任为工…...

【数据结构】栈【详解】

目录 栈的定义&#xff1a; 栈的声明与定义&#xff1a; 头文件的包含&#xff1a; 对栈的基本操作&#xff1a; 栈的初始化&#xff1a; 摧毁栈: 入栈&#xff1a; ​编辑 出栈&#xff1a; ​编辑 输出栈顶位置&#xff1a; 输出栈的当前大小&#xff1a; 判空操…...

CSS 纵向底部往上动画

<template><div class"container" mouseenter"startAnimation" mouseleave"stopAnimation"><!-- 旋方块 --><div class"box" :class"{ scale-up-ver-bottom: isAnimating }"><!-- 元素内容 --&g…...

常用的 MySQL 可视化客户端

数据库可视化客户端&#xff08;GUI&#xff09;让用户在和数据库进行交互时&#xff0c;能直观地查看、创建和修改对象&#xff0c;如&#xff1a;表、行和列。让数据库操作变得更方便了。 今天&#xff0c;我们来了解下目前市场上最常用的 MySQL 可视化客户端。 官方&#x…...

C#使用SyntaxTree获取.cs文件中的属性名和注释

有时候&#xff0c;我们可能需要获取.cs文件中的属性和对应的注释来生成一些代码&#xff0c;比如SQL查询什么的。 但使用正则匹配有时候会不准确。搜索了下&#xff0c;发现微软提供了代码解析的API。 具体如下两个方法&#xff1a; /// <summary> /// 获取所有属性和…...

基于价值认同的需求侧电能共享分布式交易策略(matlab完全复现)

目录 1 主要内容 2 部分程序 3 程序结果 4 下载链接 1 主要内容 该程序完全复现《基于价值认同的需求侧电能共享分布式交易策略》&#xff0c;针对电能共享市场的交易机制进行研究&#xff0c;提出了基于价值认同的需求侧电能共享分布式交易策略&#xff0c;旨在降低电力市…...

门控循环单元(GRU)-多输入回归预测

目录 一、程序及算法内容介绍&#xff1a; 基本内容&#xff1a; 亮点与优势&#xff1a; 二、实际运行效果&#xff1a; 三、部分程序&#xff1a; 四、全部代码数据分享&#xff1a; 一、程序及算法内容介绍&#xff1a; 基本内容&#xff1a; 本代码基于Matlab平台编译…...

电池管理系统BMS中SOC算法通俗解析(二)

下面简单介绍下我们BMS保护板使用的SOC估算方法。我们算法的主要是针对电流积分法计算SOC的局限性进行改进&#xff1a; ●电池包第一次上电使用开路电压法估算SOC。第一次上电&#xff0c;根据电池包厂家给出的电压和剩余容量二维关系图大概估算出目前电池包的剩余容量即SOC。…...

YOLOv5改进 | 2023主干篇 | 华为最新VanillaNet主干替换Backbone实现大幅度长点

一、本文介绍 本文给大家来的改进机制是华为最新VanillaNet网络&#xff0c;其是今年最新推出的主干网络&#xff0c;VanillaNet是一种注重极简主义和效率的神经网络架构。它的设计简单&#xff0c;层数较少&#xff0c;避免了像深度架构和自注意力这样的复杂操作(需要注意的是…...

爬虫工作量由小到大的思维转变---<第三十三章 Scrapy Redis 23年8月5日后会遇到的bug)>

前言: 收到回复评论说,按照我之前文章写的: 爬虫工作量由小到大的思维转变---&#xff1c;第三十一章 Scrapy Redis 初启动/conn说明书)&#xff1e;-CSDN博客 在启动scrapy-redis后,往redis丢入url网址的时候遇到: TypeError: ExecutionEngine.crawl() got an unexpected …...

PostgreSQL | 概念 | 什么是OLTPOLAP?

什么是OLTP&OLAP&#xff1f; 大白话理解&#xff1a;业务系统都可以称作OLTP&#xff0c;基于业务系统产生的数据进行数据分析和决策的都可以称为OLAP。 OLTP OLTP&#xff08; Online Transaction Processing&#xff09;在线事务处理系统 用途&#xff1a; 用于支持日…...

2023年成都市中等职业学校学生技能大赛“网络搭建及应用”赛项竞赛样卷

2023年成都市中等职业学校学生技能大赛 “网络搭建及应用”赛项竞赛样卷 &#xff08;总分1000分&#xff09; 目录 2023年成都市中等职业学校学生技能大赛 “网络搭建及应用”赛项竞赛样卷 网络建设与调试项目&#xff08;500分&#xff09; 服务器搭建与运维项目&#xff08;…...

Angular进阶之六:Progressive rendering

简介 Progressive Rendering 是一种提高 Web 应用性能的方法&#xff0c;允许页面在加载过程中逐步呈现&#xff0c;以提高用户体验。在本文中&#xff0c;我们将探讨如何在 Angular 中通过自定义指令实现 Progressive Rendering&#xff0c;特别是处理从服务器获取大量数据的…...

机器人中的数值优化之线性共轭梯度法

欢迎大家关注我的B站&#xff1a; 偷吃薯片的Zheng同学的个人空间-偷吃薯片的Zheng同学个人主页-哔哩哔哩视频 (bilibili.com) 本文ppt来自深蓝学院《机器人中的数值优化》 目录 1.无约束优化方法对比 2.Hessian-vec product 3.线性共轭梯度方法的步长​编辑 4.共轭梯度…...

嵌入式Linux C语言介绍

目录 一.前言 二.C语言的特点 一.前言 开发工具通常依赖于操作系统提供的各种功能和服务。许多开发工具都基于操作系统的API&#xff08;应用程序接口&#xff09;进行开发&#xff0c;这些API提供了文件处理、网络通信、图形界面等核心功能。没有操作系统的支持&#xff0c;…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...